Row with max 1s

Given a boolean 2D array, consisting of only 1’s and 0’s, where each row is sorted. Find the 0-based index of the first row that has the maximum number of 1’s. Return the 0-based index of the first row that has the most number of 1s. If no such row exists, return -1.

Examples :

Input: arr[][] = [[0, 1, 1, 1],[0, 0, 1, 1],[1, 1, 1, 1],[0, 0, 0, 0]] Output: 2 Explanation: Row 2 contains 4 1's (0-based indexing).
Input: arr[][] = [[0, 0], [1, 1]]
Output: 1
Explanation: Row 1 contains 2 1's (0-based indexing).
 

Expected Time Complexity: O(n+m)
Expected Auxiliary Space: O(1)

Constraints:
1 ≤ number of rows, number of columns ≤ 103
0 ≤ arr[i][j] ≤ 1 


Approach 01:

#include <vector>

using namespace std;

class Solution {
public:
    int rowWithMax1s(vector<vector<int>>& matrix) {
        int rowIndexWithMax1s = -1; // Variable to store the index of the row with the maximum number of 1s
        int columnIndex = matrix[0].size() - 1; // Start from the last column

        // Traverse through each row
        for (int rowIndex = 0; rowIndex < matrix.size(); ++rowIndex) {
            // Move left in the current row while we encounter 1s
            while (columnIndex >= 0 && matrix[rowIndex][columnIndex] == 1) {
                --columnIndex;
                rowIndexWithMax1s = rowIndex; // Update the result with the current row index
            }
        }

        return rowIndexWithMax1s; // Return the index of the row with the maximum number of 1s
    }
};
from typing import List

class Solution:
    def rowWithMax1s(self, matrix: List[List[int]]) -> int:
        rowIndexWithMax1s = -1  # Variable to store the index of the row with the maximum number of 1s
        columnIndex = len(matrix[0]) - 1  # Start from the last column

        # Traverse through each row
        for rowIndex in range(len(matrix)):
            # Move left in the current row while we encounter 1s
            while columnIndex >= 0 and matrix[rowIndex][columnIndex] == 1:
                columnIndex -= 1
                rowIndexWithMax1s = rowIndex  # Update the result with the current row index

        return rowIndexWithMax1s  # Return the index of the row with the maximum number of 1s

Time Complexity

  • Initialization:

    Initializing rowIndexWithMax1s and columnIndex takes \( O(1) \) time.

  • Traversing Rows:

    We traverse through each row of the matrix, which takes \( O(n) \) time, where \( n \) is the number of rows.

  • Traversing Columns:

    Within each row, we potentially traverse back through all the columns to find the leftmost 1. In the worst case, we move left across all columns for each row. Since each column movement only occurs once across all rows (moving strictly left across rows), the total column traversal is \( O(m) \), where \( m \) is the number of columns.

  • Overall Time Complexity:

    The overall time complexity is \( O(n + m) \), where \( n \) is the number of rows and \( m \) is the number of columns.

Space Complexity

  • Space for Variables:

    The space used by the variables rowIndexWithMax1s and columnIndex is \( O(1) \).

  • Input Matrix:

    The input matrix is not modified, so no additional space is required for the input data.

  • Overall Space Complexity:

    The overall space complexity is \( O(1) \).

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top