The problem
In a grid sorted in decreasing order along every row and every column, count the negative numbers.
Input: 4,3,2,−1 / 3,2,1,−1 / 1,1,−1,−2 / −1,−1,−2,−3 Output: 8
Picture it
Picture a staircase walk starting at the bottom-left. If the reading is negative, everything to its right in that row is negative too: count them all and step up. Otherwise step right. The walk never retraces, so it’s fast.
Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.
The key idea
Staircase search from a corner: O(rows + cols).
Python solution
def count_negatives(grid): # rows and columns decrease
r, c = len(grid) - 1, 0
count = 0
while r >= 0 and c < len(grid[0]):
if grid[r][c] < 0:
count += len(grid[0]) - c
r -= 1
else:
c += 1
return countIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.