Find row with maximum 1's

·#2643·Medium·Binary Search

Use binary search on each row to count 1s efficiently

Asked at:AmazonMicrosoft

Practice mode

Step

Current step

Initialize tracking variables: cnt_max = 0, index = -1.

Matrix workspace

Binary Search

Step 1 / 30init

100%

Input Matrix

Max 1s =

Row Index =

-1

step 1 / 30

Space play← → stepHome reset

TimeO(n log m)·SpaceO(1)

Binary Search

1class Solution {
2    lowerBound(arr, n, x) {
3        let low = 0, high = n - 1;
4        let ans = n;
5        while (low <= high) {
6            let mid = Math.floor((low + high) / 2);
7            if (arr[mid] >= x) {
8                ans = mid;
9                high = mid - 1;
10            } else {
11                low = mid + 1;
12            }
13        }
14        return ans;
15    }
16    
17    rowWithMax1s(mat) {
18        let n = mat.length;
19        let m = mat[0].length;
20        
21        let cnt_max = 0; 
22        let index = -1;  
23 //n: 4m: 4cnt_max: 0index: -1
24        for (let i = 0; i < n; i++) {
25            let cnt_ones = m - this.lowerBound(mat[i], m, 1);
26            if (cnt_ones > cnt_max) {
27                cnt_max = cnt_ones;
28                index = i;
29            }
30        }
31        return index;
32    }
33}

cnt_max0

index-1

Command Palette

Find row with maximum 1's

Find row with maximum 1's