Advertisement
kai-rocket

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!
Python 1.67 KB | None
  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] < 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.                
  45.         # Return total num of neg nums
  46.         return num_neg_nums
  47.        
Advertisement
RAW Paste Data Copied
Advertisement