CODEWITHSUNDEEP
algorithmmatrix
zynsteve
zynsteve

Reputation: 21

Given a matrix which only contains 0 and 1, and each row of the matrix is sorted, please find which row contains the most 1s

Given a matrix which only contains 0 and 1, and each row of the matrix is sorted, please find which row contains the most 1s. For a M*N matrix, O(M+N) time complexity is required, and O(1) space complexity is required.

Example

Input:

000000011111

000011111111

000000111111

000000000111

000000011111

000011111111

Output:

As row 2 and row 6 both contain 8 1s, the output is [2,8],[6,8].

I came up a solution:

public List<List<Integer>> mostOnes(int[][] a) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    for (int j = 0; j < a[0].length; j++) {
        for (int i = 0; i < a.length; i++) {
            if (a[i][j] == 1) {
                List<Integer> res = new ArrayList<>(); 
                res.add(i + 1);
                res.add(a[0].length - j);
                result.add(res);
            }
        }
        if (result.size() != 0) break;
    }
    return result;
}

However, it is not O(M+N). Does anyone have other solutions?

Upvotes: 2

Views: 419

Answers (2)

user1196549
user1196549

Reputation:

The solution goes as follows:

Q= 0
For every row,
    Search the next Q backward, starting from N - Q
    Set the new Q there.

This process stops with Q indicating the largest number of 1's.

As the searches are performed by decreasing indexes from N down to 0 (at worst), and this is split between the M rows, the complexity is O(N + M). The trick is to continue the search from one row to the next staying in the current column rather than restarting from the edge.

Q= 0
for j in range(M):
    for i in range(Q):
        if A[j][N - 1 - i] == '0':
            break

(Not guaranteed to be exact in details, but the working principle is there.)

0000000|11111
0000|11111111
0000|00111111
0000|00000111
0000|00011111
0000|11111111

Upvotes: 2

abdullah
abdullah

Reputation: 662

Please check my O(m + n) implementation. The code is written in C, but easily you can convert it to Java.

int FindRow(vector<vector<int>>& mat) {
    int m = mat.size(), n = mat[0].size();
    int i = 0, j = n - 1, mx = 0;
    while (i < m && j >= 0) {
        while (j >= 0 && mat[i][j] == 1) --j;
        mx = max(mx, n - j - 1);
        ++i;
    }
    return mx;
}

I have started with first row and last column. When I get first 0, I move to next row. We should check only remaining columns at most.

Upvotes: 0

Related Questions