Pattern visualizer
Row with Maximum 1s
Counting the 1s in every row reads all rows*cols cells, which throws away the one fact the problem hands you: each row is sorted. In a sorted 0s-then-1s row, the count is decided entirely by where the first 1 begins, and binary search finds that boundary in log(cols) probes instead of scanning. The second idea is what makes it fast in practice: keep the best boundary found so far as `edge` and never probe at or right of it, because a 1 starting there can only tie, never win. Rows after a strong row therefore get cheaper and cheaper. Animated on: mat = [[0,0,0,1],[0,1,1,1],[0,0,0,0],[0,0,1,1]] — every row is sorted (0s then 1s); find the row holding the most 1s. Shown flattened row-major..
Binary search each row, but only left of the best edge so far
A 4x4 matrix whose every row is sorted — all its 0s first, then all its 1s — shown flattened row-major, so row r column c sits at index r*4+c. A row has more 1s exactly when its first 1 starts further left, so the whole question is which row's first-1 column is smallest. edge = 4 means no 1 has been found yet, so all 4 columns are still worth probing.
1FUNCTION rowWithMaxOnes(mat):2 best <- -13 edge <- COLS(mat)4 FOR r <- 0 TO ROWS(mat) - 1:5 lo <- 06 WHILE lo < edge:7 mid <- (lo + edge) / 28 IF mat[r][mid] = 1:9 edge <- mid10 best <- r11 ELSE:12 lo <- mid + 113 RETURN best
← / → step · space play · Home restart