Leetcode 2643: Row With Maximum Ones

Input: The input consists of a binary matrix 'mat' with m rows and n columns. Each element in the matrix is either 0 or 1.

Example: mat = [[0, 1, 1], [1, 0, 1], [1, 1, 1]]

Constraints:

• 1 <= m, n <= 100

• mat[i][j] is either 0 or 1

Output: Return an array containing two integers: the index of the row with the maximum count of 1's and the number of 1's in that row.

Example: Output: [2, 3]

Constraints:

• The output array should contain the row index and the count of 1's in the selected row.

Goal: The goal is to find the row with the maximum number of 1's and return its index along with the count of 1's in that row.

Steps:

• Step 1: Initialize a variable to track the maximum count of 1's and the corresponding row index.

• Step 2: Traverse each row of the matrix and count the number of 1's in the row.

• Step 3: If the count of 1's in the current row exceeds the previous maximum, update the row index and the maximum count.

• Step 4: After processing all rows, return the row index and the count of 1's in the row with the maximum count.

Goal: The solution must efficiently process matrices up to size 100 x 100, and handle cases where all elements are 0's or 1's.

Steps:

• Ensure the solution operates in O(m * n) time, where m is the number of rows and n is the number of columns.

Assumptions:

• The matrix contains only 0's and 1's.

• Input: Input: mat = [[0, 1, 1], [1, 0, 1], [1, 1, 1]]

• Explanation: The first row has 2 ones, the second row has 2 ones, and the third row has 3 ones. The row with the maximum count of 1's is the third row (index 2), so the output is [2, 3].

Approach: We will iterate through each row of the binary matrix and count the number of 1's. As we process each row, we track the maximum count of 1's and its corresponding row index. The result is returned once all rows have been evaluated.

Observations:

• Since the problem is about counting 1's in each row, a straightforward approach of iterating through the matrix should suffice.

• We need to ensure that the solution is efficient enough to handle matrices of size 100 x 100.

Steps:

• Step 1: Initialize two variables to track the maximum count of 1's and the index of the corresponding row.

• Step 2: Loop through each row in the matrix. For each row, count the number of 1's.

• Step 3: If the count of 1's in the current row exceeds the previous maximum, update the maximum and the row index.

• Step 4: After processing all rows, return the row index and the count of 1's in that row.

Empty Inputs:

• If the matrix has no rows or columns, handle it appropriately.

Large Inputs:

• For larger matrices, ensure that the solution works efficiently within the given constraints.

Special Values:

• If all rows contain no 1's, return the first row with 0 ones.

Constraints:

• The algorithm should run in linear time, O(m * n), where m is the number of rows and n is the number of columns.

vector<int> rowAndMaximumOnes(vector<vector<int>>& mat) {
    int m = mat.size(), n = mat[0].size();
    int mx = 0, idx = 0;
    for(int i = 0; i < m; i++) {
        int cnt = 0;
        for(int j = 0; j < n; j++)
            if(mat[i][j]) cnt++;
        if(cnt > mx) {
            idx = i;
            mx = cnt;
        }
    }
    return vector<int>{idx, mx};
}

1 : Function Declaration

vector<int> rowAndMaximumOnes(vector<vector<int>>& mat) {

The function is declared with a vector of vectors `mat` as the input, representing a binary matrix, and it returns a vector of integers containing the index of the row with the maximum 1's and the count of 1's.

2 : Variable Initialization

    int m = mat.size(), n = mat[0].size();

Here, the number of rows `m` and columns `n` of the matrix are obtained by using the `size()` function.

3 : Variable Initialization

    int mx = 0, idx = 0;

Two variables are initialized: `mx` (to store the maximum count of 1's found) and `idx` (to store the index of the row with the maximum 1's).

4 : Loop Initialization

    for(int i = 0; i < m; i++) {

A loop is started to iterate through each row of the matrix.

5 : Variable Initialization

        int cnt = 0;

A variable `cnt` is initialized to count the number of 1's in the current row.

6 : Inner Loop

        for(int j = 0; j < n; j++)

An inner loop starts to iterate through each column of the current row.

7 : Condition

            if(mat[i][j]) cnt++;

If the current element of the matrix is 1, increment the counter `cnt`.

8 : Comparison

        if(cnt > mx) {

If the count of 1's in the current row is greater than the previous maximum (`mx`), proceed to update the values.

9 : Variable Update

            idx = i;

Update `idx` to the current row index `i` as it now has the highest count of 1's.

10 : Variable Update

            mx = cnt;

Update the maximum count of 1's found so far with the current row's count `cnt`.

11 : Return Statement

    return vector<int>{idx, mx};

Return a vector containing the index of the row with the maximum 1's and the count of 1's.

Best Case: O(m * n)

Average Case: O(m * n)

Worst Case: O(m * n)

Description: The time complexity is O(m * n) because we are iterating through all elements in the matrix.

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is O(1) because we are only using a few variables to track the result, and no additional data structures are required.

Leetcode 2643: Row With Maximum Ones

Explore →