← DiffPush

Row with maximum number of 1's

Baseline Binary Search · 2D Arrays O(n + m) · O(1)

The Busiest Lane on the Sorting Floor

A parcel sorter feeds lanes with pass/fail flags, and each lane's flags arrive sorted - failures first, passes after. Supervision wants the first lane with the most passes to route rush parcels down it. Exploit the sorted flags to sweep the grid without rescanning every lane.

Input: An integer n, an integer m, and an n x m boolean matrix Arr where every row is sorted (0s before 1s).

Output: The 0-indexed number of the first row containing the most 1s, or -1 when the grid holds no 1s at all.

Constraints

• 1 <= n, m <= 100
• 0 <= Arr[i][j] <= 1
• Each row is sorted in non-decreasing order

Examples

Example 1

Input: {"n":4,"m":4,"Arr":[[0,1,1,1],[0,0,1,1],[1,1,1,1],[0,0,0,0]]}
Output: 2
Lane 2 passes every parcel, four in total, the most on the floor.

Example 2

Input: {"n":2,"m":2,"Arr":[[0,0],[1,1]]}
Output: 1
Only the second lane passes anything, so it wins with two passes.

Solve this in your browser →

Also on LeetCode ↗