You are given an n x n binary matrix arr — every cell holds a 0 or a 1 — and every row is sorted in non-decreasing order, meaning all the 0s in a row come before all the 1s.
Return the 0-based index of the first row that contains the maximum number of 1s. If the matrix contains no 1s at all, return -1.
Note:
n denotes both the number of rows and the number of columns.O(n²). Sortedness means each row's 1s form a suffix, so the count is cols - firstOneIndex: binary search finds that boundary in O(log n), and the staircase walk amortizes it to O(1) per row.1, so you must inspect all of them — the O(n²) scan becomes optimal. Sortedness is exactly what buys the speedup, which is why confirming it up front matters.Input: n = 4, arr = [[0,1,1,1],[0,0,1,1],[1,1,1,1],[0,0,0,0]] Output: 2 Row 2 holds four 1s — more than any other row.
Input: n = 2, arr = [[0,0],[1,1]] Output: 1 Row 1 has two 1s; row 0 has none.
Input: n = 2, arr = [[0,0],[0,0]] Output: -1 There are no 1s anywhere, so no row qualifies.
- 1 <= n <= 10^3 - arr[i][j] is either 0 or 1 - Every row of arr is sorted in non-decreasing order
A binary matrix, a sorted guarantee, and one question: which row has the most 1s? The journey from count everything to a single sliding pointer is one of the prettiest speedups in matrix problems — and the final trick reappears all over sorted-matrix interviews.
In plain English: every row's 1s are bunched at the right end, so the count of 1s in a row is n - (index of the first 1). We want the first row that maximises that count — or -1 if no 1 exists anywhere.
Worked example — n = 4, arr = [[0,1,1,1],[0,0,1,1],[1,1,1,1],[0,0,0,0]]
col→ 0 1 2 3 row 0: 0 1 1 1 → three 1s row 1: 0 0 1 1 → two 1s row 2: 1 1 1 1 → four 1s ✓ maximum row 3: 0 0 0 0 → zero 1s answer: 2
Asking two or three sharp questions before touching the keyboard shows the interviewer you hunt for guarantees, not just patterns.
“Is every row guaranteed to be sorted in non-decreasing order?”
The entire speedup rests on this. On an unsorted row, both the binary search and the staircase walk silently return wrong answers rather than failing loudly.
“Are the values strictly 0 and 1?”
The counting trick — count equals columns minus the first-1 index — only works for binary rows.
“What should I return if the matrix has no 1s at all?”
Return -1. The staircase solution detects this for free: the pointer never moves, so the answer is never updated.
“If two rows tie on the count, which index wins?”
The smallest one. Your update rule must fire only on a strictly larger count, or you will return the last maximum instead of the first.
“How large can n get?”
Up to 10^3, so the O(n^2) scan is about 10^6 cells and technically passes — but the interviewer is fishing for the O(n log n) or O(n) idea that exploits sortedness.
Before I code, I want to confirm the guarantees.
Each row is individually sorted, so within a row every 0 comes before every 1 — correct?
If no row contains a 1 I will return -1, and on a tie I will return the smallest row index.
Sorted non-decreasing with only 0s and 1s means every row looks like 0 0 … 0 1 1 … 1. So a row is fully described by one number — the index of its first 1 — and its count of 1s is n - firstOne. Comparing rows means comparing boundaries, not counting cells.
row: 0 0 1 1 1
↑ firstOne = 2 → count = 5 − 2 = 3Each row is sorted, so the first 1 is found with a lower-bound binary search in O(log n). Doing this for every row gives O(n log n) — already a big win over scanning all n² cells.
Keep a column pointer j at the current best boundary. Row i beats the champion iff arr[i][j] == 1 — a 1 at the champion's boundary means this row's 1s start even further left. When that happens, slide j left past this row's 1s; when it does not, drop straight down. j never moves right again, so the total sliding across all rows is at most n steps: the whole matrix is solved in O(n + n) — a staircase walk from the top-right corner.
| Brute force | Binary search | Staircase | |
|---|---|---|---|
| Time | O(n²) | O(n log n) | O(n) |
| Space | O(1) | O(1) | O(1) |
The full, runnable code for each approach — with a dry run — lives in the Approaches selector below.
Key takeaway
When each row of a matrix is sorted, a whole row compresses to a single number — its boundary index. Track the best boundary with a pointer that only moves one way and the 2D problem collapses to a linear walk. This top-right staircase is the same move that cracks many sorted-matrix search problems.
j ← n − 1, ans ← −1
for i ← 0 … n−1:
while j ≥ 0 and arr[i][j] == 1:
j ← j − 1 # boundary improves — slide left
ans ← i # row i is the new champion
return ans