PPractick

The problem

A factory's quality dashboard stores each production line's test results as a row of 0s and 1s, sorted so that the failures (0) come first and the passes (1) come after. The manager wants the line with the most passes, and if several tie, the one with the smallest index. Counting every cell is O(n × m). Because each row is sorted, the number of 1s in a row is m − (index of the first 1), which binary search finds in O(log m). An even slicker O(n + m) walk starts at the top-right corner and moves left or down.

Example: [[0, 1, 1, 1], [0, 0, 1, 1], [1, 1, 1, 1], [0, 0, 0, 0]] → 2.

Function signature

int rowWithMax1s(const vector<vector<int>>& grid);  // row index, first on ties, -1 if there are no 1s

Test cases

Input grid	Output	Explanation
[[0,1,1,1],[0,0,1,1],[1,1,1,1],[0,0,0,0]]	2	Row 2 has four 1s
[[0,0],[1,1]]	1
[[0,0],[0,0]]	-1	No 1s anywhere
[[0,1],[0,1],[1,1]]	2
[[1]]	0
[[0,1,1],[0,1,1]]	0	Tie: the first row wins

(Confirm: every row is sorted with 0s before 1s; return the first row on ties; -1 if there are no 1s.)

How interviewers phrase it

• "Find the row with the maximum number of 1s in a row-wise sorted binary matrix" (GeeksforGeeks).
• A check that you can exploit per-row sortedness, and ideally find the O(n + m) staircase walk.

Clarifying questions to ask

1. Is each row sorted (all 0s then all 1s)?
2. What to return on ties, and when there are no 1s at all?
3. What are the dimensions? (Decides between O(n log m) and O(n + m).)

Follow-ups to expect

1. "How do you count 1s in a sorted row quickly?"
2. "Can you do better than O(n log m)?"
3. "Why does the staircase keep the first row on ties?"
4. "Complexity?"

Related questions

• Search in a 2D matrix Medium
• Search in 2D matrix - II Medium
• Find Peak Element - II Medium
• Matrix Median Medium
• Swim in Rising Water Medium
• Search X in sorted array Easy

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in