Pattern visualizer
Count Negative Numbers in a Sorted Matrix
Scanning every cell works but ignores the sorting entirely. Start at the bottom-left instead: moving right only ever increases the value and moving up only ever increases it too, so the bottom-left corner is the smallest value reachable by that walk. When the current cell is negative, the whole rest of that row is negative (rows are non-increasing), so count the slice in one step and move up to a row that can't repeat it. When it isn't negative, move right — nothing to the left could have been negative either, since it would already have been found. Each cell is visited at most once, so the walk is O(m+n). Animated on: matrix = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]] — every row and column sorted non-increasing. Count the negative entries..
Staircase walk from the bottom-left corner — O(m+n), no extra memory
4x4 matrix, sorted non-increasing along every row and column
Start at the bottom-left corner (3,0) — moving right only increases the value, moving up only increases it too, so this cell is the smallest reachable by that walk.
1FUNCTION countNegatives(matrix):2 n <- LENGTH(matrix[0])3 row <- LENGTH(matrix) - 14 col <- 05 count <- 06 WHILE row >= 0 AND col < n:7 IF matrix[row][col] < 0:8 count <- count + (n - col)9 row <- row - 110 ELSE:11 col <- col + 112 RETURN count
← / → step · space play · Home restart