algoadvance

Leetcode 2643. Row With Maximum Ones

Problem Statement

You are given a rectangular matrix grid of size m x n, where each cell contains either 0 or 1.

Return the row number of the row with the maximum number of 1s. If there are multiple rows with the same number of 1s, return the index of the first such row.

You may assume that the matrix grid has at least one row and one column.

Example:

Input: grid = [[0,1,1,0],[0,0,0,0],[0,1,1,1]]
Output: 2
Explanation: The row indexed 2 has 3 ones, which is the maximum.

Clarifying Questions

1. Can there be an empty matrix?
   • No, the problem assumes the matrix has at least one row and one column.
2. Are there constraints on the grid size?
   • We are assuming typical constraints for such problems, e.g., the number of rows and columns being in the range [1, 1000].
3. How are ties handled?
   • The row with the lowest index (i.e., first occurring row) should be returned in case of a tie.

Strategy

1. Initialize two variables to keep track of the row number with the maximum number of 1s and the maximum count of 1s encountered so far.
2. Iterate through each row of the grid.
3. For each row, count the number of 1s.
4. Update the row index and maximum count if the current row has more 1s compared to the previous maximum count.
5. Return the row index with the maximum number of 1s.

Code

public class MaximumOnesRow {
    public int rowWithMaxOnes(int[][] grid) {
        int maxOnesRowIndex = -1;
        int maxOnesCount = -1;
        
        for (int i = 0; i < grid.length; i++) {
            int count = 0;
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    count++;
                }
            }
            if (count > maxOnesCount) {
                maxOnesCount = count;
                maxOnesRowIndex = i;
            }
        }
        
        return maxOnesRowIndex;
    }
    
    public static void main(String[] args) {
        MaximumOnesRow solution = new MaximumOnesRow();
        
        int[][] grid1 = {
            {0, 1, 1, 0},
            {0, 0, 0, 0},
            {0, 1, 1, 1}
        };
        
        System.out.println(solution.rowWithMaxOnes(grid1)); // Output: 2
        
        int[][] grid2 = {
            {0, 1, 1},
            {1, 1, 1},
            {0, 0, 1}
        };
        
        System.out.println(solution.rowWithMaxOnes(grid2)); // Output: 1
    }
}

Time Complexity

• The time complexity of the solution is O(m * n), where m is the number of rows and n is the number of columns. This is because we are iterating through each cell of the matrix exactly once.
• Space complexity is O(1), as we are only using a constant amount of extra space.

This approach ensures that we efficiently determine the row with the most 1s while adhering to the constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?