Row with Max 1s in Rowwise Sorted

Binary search each row, but only left of the best edge so far

time O(rows * log cols)space O(1)

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.

Details

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.

Problem:Row with Max 1s in Rowwise SortedMedium

Binary search each row, but only left of the best edge so far

step 1 / 12

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

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.

Pseudocode

1FUNCTION rowWithMaxOnes(mat):
2  best <- -1
3  edge <- COLS(mat)
4  FOR r <- 0 TO ROWS(mat) - 1:
5    lo <- 0
6    WHILE lo < edge:
7      mid <- (lo + edge) / 2
8      IF mat[r][mid] = 1:
9        edge <- mid
10        best <- r
11      ELSE:
12        lo <- mid + 1
13  RETURN best

← / → step · space play · Home restart

Every step in words

Show all 12 steps

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.
Row 0, column 2 (index 2) is a 0. The row is sorted, so every column at or left of 2 is a 0 too and none of them can hold this row's first 1 — that discards 3 columns in one probe: lo <- 3.
Row 0, column 3 (index 3) holds a 1, the first 1 found anywhere so far — so row 0 holds at least 1 one, which is more than nothing. edge <- 3, best <- 0. Only columns left of 3 could push that edge further, so the window is now empty and this row is settled.
Row 0's window is empty: nothing left of column 3 is a 1, so 3 really is where its 1s begin — 1 one, the most so far, so best is row 0. Every later row now probes only columns 0..2, because a 1 starting at 3 or later could at best tie.
Row 1, column 1 (index 5) holds a 1, and 1 sits left of the best edge so far, 3 — so row 1 holds at least 3 ones, beating every row before it. edge <- 1, best <- 1. Only columns left of 1 could push that edge further, so the window is now columns 0..0.
Row 1, column 0 (index 4) is a 0. The row is sorted, so every column at or left of 0 is a 0 too and none of them can hold this row's first 1 — that discards 1 column in one probe: lo <- 1.
Row 1's window is empty: nothing left of column 1 is a 1, so 1 really is where its 1s begin — 3 ones, the most so far, so best is row 1. Every later row now probes only columns 0..0, because a 1 starting at 1 or later could at best tie.
Row 2, column 0 (index 8) is a 0. The row is sorted, so every column at or left of 0 is a 0 too and none of them can hold this row's first 1 — that discards 1 column in one probe: lo <- 1.
Row 2's window closed with no 1 left of column 1, so row 2 holds at most 3 ones — a tie at best, never a win, so row 1 keeps the lead. It cost only 1 column of search instead of all 4: the winner's edge shrinks the work for every row after it.
Row 3, column 0 (index 12) is a 0. The row is sorted, so every column at or left of 0 is a 0 too and none of them can hold this row's first 1 — that discards 1 column in one probe: lo <- 1.
Row 3's window closed with no 1 left of column 1, so row 3 holds at most 3 ones — a tie at best, never a win, so row 1 keeps the lead. It cost only 1 column of search instead of all 4: the winner's edge shrinks the work for every row after it.
All 4 rows are searched. Row 1's 1s start at column 1 — earlier than any other row manages — which gives it 3 ones, so row 1 is the answer.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Row with Max 1s in Rowwise Sorted in the editor All Binary Search problems Back to roadmap