 # Count Negative Numbers in a Sorted Matrix

Mar 26th, 2021
579
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. class Solution:
2.     def countNegatives(self, grid: List[List[int]]) -> int:
3.         # Naive
4.
5.         # Keep track of num neg numbers so far
6.         num_neg_nums = 0
7.
8.         # Loop through each row
9.         for row in grid:
10.
11.             # If first elem in row is neg, whole row is neg
12.             if row < 0:
13.                 num_neg_nums += len(row)
14.                 continue
15.
16.             # If last elem in row is pos, whole row is pos
17.             if row[-1] >= 0:
18.                 continue
19.
20.             # Binary search to find lowest positive number in that row
21.             # Initialise bounds
22.             left_index = 0
23.             right_index = len(row) - 1
24.             # Binary search loop
25.             while left_index <= right_index:
26.
27.                 # Find mid index and number within bounds
28.                 mid_index = (left_index + right_index) // 2
29.                 mid_num = row[mid_index]
30.
31.                 # If mid num is non-negative and next number is negative
32.                 if mid_num >= 0 and row[mid_index + 1] < 0:
33.                     # Add num neg numbers in row to total
34.                     num_neg_nums += len(row) - (mid_index + 1)
35.                     break
36.
37.                 # If mid num is negative, move to the left
38.                 if mid_num < 0:
39.                     right_index = mid_index - 1
40.
41.                 # If mid num is not negative, move to the right
42.                 else:
43.                     left_index = mid_index + 1
44.