Row With Maximum Ones - Leetcode Solution

Problem Statement:

You are given a binary matrix A where each row of the matrix represents a sorted array of 0s and 1s. The matrix is sorted in a non-decreasing order of the number of 1s present in each row. Find the row with the maximum number of 1s. If two or more rows have the same maximum number of 1s, return the row with the smallest index.

Example:

A = [[0,1,1,1],[0,0,1,1],[0,0,0,1],[0,0,0,0]]

Output: 2

Explanation: The matrix is as follows:

0 1 1 1 0 0 1 1 0 0 0 1 0 0 0 0

The row with the maximum number of 1s is the second row with three 1s.

Solution:

The given binary matrix is sorted in non-decreasing order of the number of 1s present in each row. This means that the first row will have the minimum number of 1s and the last row will have the maximum number of 1s. We can start from the last row and count the number of 1s in each row. The row with the maximum number of 1s will be the answer.

Algorithm:

1. Initialize variables max_ones and row_index to -1.
2. Iterate through each row of the matrix starting from the last row: a. Count the number of ones in the current row. b. If the number of ones in the current row is greater than max_ones: i. Update max_ones to the number of ones in the current row. ii. Update row_index to the index of the current row. c. Continue iterating.
3. Return row_index as the answer.

Time Complexity: O(mn) where m is the number of rows and n is the number of columns.

Space Complexity: O(1)

Code:

Python:

class Solution: def findMaxConsecutiveOnes(self, nums: List[int]) -> int: max_ones = -1 row_index = -1

    for i in range(len(nums)-1, -1, -1):
        ones_count = sum(nums[i])
        if ones_count > max_ones:
            max_ones = ones_count
            row_index = i
    
    return row_index

Java:

class Solution { public int findMaxConsecutiveOnes(int[][] matrix) { int max_ones = -1; int row_index = -1;

    for (int i=matrix.length-1; i>=0; i--) {
        int ones_count = 0;
        for (int j=0; j<matrix[i].length; j++) {
            ones_count += matrix[i][j];
        }
        if (ones_count > max_ones) {
            max_ones = ones_count;
            row_index = i;
        }
    }
    
    return row_index;
}

}

1