Number Negatives in Sorted Matrix

Find the number of negative integers in a matrix that is sorted row-wise and column-wise.

input:
t1 = [[-3, -2, -1, 1],
      [-2, 2, 3, 4],
      [4, 5, 7, 8]]

output:
4

The Idea: We can scan the array in O(n*m) time and count the negatives. Alternatively, we can begin from the top right corner, find the first negative iterating backwards, use that position to find the remaining negatives in that row, and then move down one row, and continue this process until we reach the last row. We have to understand why we can move down a row from the first negative position of the previous row. This can be proved inductively. Consider only two rows. In the case that there are all positives, the algorithm will terminate. In the case of negatives, the position in the second row above the previous negative would have to be greater than or equal to it. That means, if the previous number was negative, the the following number can only be as small as that negative, and since the previous number was the largest negative, the next negative must be >= this element. The same logic can be said about the remaining rows. We can integrate in binary partition to find the next negative given these knew bounds.

.-----------.  <- b_search
-3, -2, -1, 1
.--------.     <- b_search
-2,  2,  3, 4
.-.            <- b_search
 4,  5,  7, 8

Complexity: O(log(n+m)) time (?) Not too sure,

def b_search(ar, left, right):
    """
    :param ar: List[int]
    :param left: int
    :param right: int
    :return: int
    """
    if left <= right:
        mid = int(left + (right - left) / 2)
        if ar[mid] >= 0 and mid - 1 >= 0 and ar[mid - 1] < 0:
            return mid - 1
        # checking the edges of the array
        elif mid == right and ar[mid] < 0:
            return right
        # both are positive, so search left, otherwise search right
        elif ar[mid] >= 0 and mid - 1 >= 0 and ar[mid - 1] >= 0:
            return b_search(ar, left, mid - 1)
        else:
            return b_search(ar, mid + 1, right)
    else:
        return -1


def count_negatives(matrix):
    """
    :param matrix: List[List[int]]
    :return: int
    """
    r = 0
    c = len(matrix[0]) - 1
    n_negs = 0

    while r < len(matrix):
        neg_i = b_search(matrix[r][:c + 1], 0, c)
        if neg_i != -1:
            n_negs += neg_i + 1
            r += 1
            c = neg_i
        else:
            return n_negs
    return n_negs


t1 = [[-3, -2, -1, 1],
      [-2, 2, 3, 4],
      [4, 5, 7, 8]]

t2 = [[-3, -2, -1, -1],
      [-2, -2, 3, 4],
      [-1, 5, 7, 8]]

t3 = [[-1, -1, -1, -1, -1],
      [-1, -1, -1, -1, -1],
      [-1, -1, -1, -1, -1]]

t4 = [[]]

t5 = [[-4, -3, -1, -1]]

t6 = [[-1, -1, -1]]

t7 = [[-1]]

t8 = [[1, 2, 3, 4]]

t9 = [[1]]

print(count_negatives(t1))
print(count_negatives(t2))
print(count_negatives(t3))
print(count_negatives(t4))
print(count_negatives(t5))
print(count_negatives(t6))
print(count_negatives(t7))
print(count_negatives(t8))
print(count_negatives(t9))