easy Problem 3 Row With Maximum Ones

Problem Statement

Given a binary matrix that has dimensions , consisting of ones and zeros. Determine the row that contains the highest number of ones and return two values: the zero-based index of this row and the actual count of ones it possesses.

If there is a tie, i.e., multiple rows contain the same maximum number of ones, we must select the row with the lowest index.

Examples

Example 1:

• Input: [[1, 0], [1, 1], [0, 1]]
• Expected Output: [1, 2]
• Justification: The second row [1, 1] contains the most ones, so the output is [1, 2].

Example 2:

• Input: [[0, 1, 1], [0, 1, 1], [1, 1, 1]]
• Expected Output: [2, 3]
• Justification: The third row [1, 1, 1] has the most ones, leading to the output [2, 3].

Example 3:

• Input: [[1, 0, 1], [0, 0, 1], [1, 1, 0]]
• Expected Output: [0, 2]
• Justification: Both the first and third rows contain two ones, but we choose the first due to its lower index, resulting in [0, 2].

Constraints:

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 100
• mat[i][j] is either 0 or 1.

Pattern

Row-wise aggregate scan with tie → lowest index. Brute force counts 1s per row in O(m·n). If rows are sorted (0s then 1s) — the common LeetCode follow-up — binary-search the first 1 in each row for O(m log n). Update only on strict greater counts so ties keep the earlier index. Empty-of-ones matrix correctly returns [0, 0] under this init.

Solution

For each row, sum the 1s (or count them). If that count is strictly greater than the best so far, record the row index and count. One full pass is O(m·n) time and O(1) extra space — optimal when rows are unsorted because every cell can hold a 1.

Step-by-Step Algorithm

1. Initialize Variables: Set up two variables: maxOnesCount, initially 0, for tracking the maximum number of 1s found in any row; and maxOnesIdx, initially 0, for storing the index of the row with this maximum count.

2. Iterate Through Each Row: Loop through each row of the matrix. For every row, perform the following steps:

   a. Count 1s in the Current Row: Initialize a counter for the number of 1s in this row. Traverse through each element of the row, incrementing the counter for each 1 encountered.

   b. Update Maximum Count and Row Index: If the count of 1s in the current row exceeds maxOnesCount, update maxOnesCount with the new count and set maxOnesIdx to the current row's index.

3. Handling No 1s Scenario: If no 1s are found in the entire matrix, maxOnesIdx and maxOnesCount remain 0.

4. Return the Result: At the end of the iteration, return [maxOnesIdx, maxOnesCount].

Algorithm Walkthrough

• Initialize maxOnesIdx to 0 and maxOnesCount to 0.
• Loop through each row:
  • Row 0 [1, 0, 1]: Count of ones = 2. It is greater than maxOnesCount so update maxOnesIdx to 0 and maxOnesCount to 2.
  • Row 1 [0, 0, 1]: Count of ones = 1. It is not greater than maxOnesCount, no update occurs.
  • Row 2 [1, 1, 0]: Count of ones = 2. It is equal to maxOnesCount, so no update occurs to maintain the smallest index.
• Return [maxOnesIdx, maxOnesCount] which yields [0, 2].

Here is the visual representation of the algorithm:

Code

Here is the code for this algorithm:

public class Solution {

  public int[] findMaxOnesRow(int[][] mat) {
    int maxOnesIdx = 0;
    int maxOnesCount = 0;
    // Traverse through rows
    for (int i = 0; i < mat.length; i++) {
      int onesCount = 0;
      // Count ones in the current row
      for (int j = 0; j < mat[i].length; j++) {
        onesCount += mat[i][j];
      }
      // Check and update tracking variables if needed
      if (onesCount > maxOnesCount) {
        maxOnesIdx = i;
        maxOnesCount = onesCount;
      }
    }
    return new int[] { maxOnesIdx, maxOnesCount };
  }

  // Main method for testing
  public static void main(String[] args) {
    Solution sol = new Solution();
    // Applying example inputs
    int[] result1 = sol.findMaxOnesRow(
      new int[][] { { 1, 0 }, { 1, 1 }, { 0, 1 } }
    );
    System.out.println(result1[0] + ", " + result1[1]); // Output: 1, 2

    int[] result2 = sol.findMaxOnesRow(
      new int[][] { { 0, 1, 1 }, { 0, 1, 1 }, { 1, 1, 1 } }
    );
    System.out.println(result2[0] + ", " + result2[1]); // Output: 2, 3

    int[] result3 = sol.findMaxOnesRow(
      new int[][] { { 1, 0, 1 }, { 0, 0, 1 }, { 1, 1, 0 } }
    );
    System.out.println(result3[0] + ", " + result3[1]); // Output: 0, 2
  }
}

Complexity Analysis

Time Complexity

• Outer loop (rows): The outer loop iterates through each row of the matrix. If there are M rows, this loop runs times.

• Inner loop (columns): For each row, the inner loop counts the number of ones by iterating through all the columns. If each row has N columns, the inner loop runs times for each row.

• Therefore, the total time complexity is , where M is the number of rows and N is the number of columns in the matrix.

Overall time complexity: .

Space Complexity

• Constant space: The algorithm uses a few additional variables (maxOnesIdx, maxOnesCount, and onesCount), all of which require constant space, .

• The result array new int[]{maxOnesIdx, maxOnesCount} also takes constant space, .

Overall space complexity: .

🎯 STRICT STANDOUT — Row With Maximum Ones

1. Why / judgment

Scan rows; keep best count; update only on strict greater so ties preserve lowest index. Unsorted rows force reading every cell (Θ(mn)). Sorted rows (0s then 1s) unlock binary search first-1 → Θ(m log n).

2. Hand-run + complexity (K11)

mat = [[1,0,1],[0,0,1],[1,1,0]]
i=0 count=2 → bestIdx=0 best=2
i=1 count=1 → no
i=2 count=2 → equal, no update (strict >) → [0,2] ✓

Ex1 [[1,0],[1,1],[0,1]]: counts 1,2,1 → [1,2]

Unsorted: outer m rows × n cols → Θ(m·n) time, Θ(1) space
Lower bound: each cell can be a 1; must read all → Θ(mn) optimal without row structure
Sorted rows: first 1 via binary search per row → Θ(m log n) comparisons
If also left-heavy (more 1s → first 1 earlier), staircase O(m+n) from top-right possible.

3. Pattern — ROW AGGREGATE + TIE → MIN INDEX (K12)

Name: Argmax row sum with stable min index.

Recognition: binary matrix; report row index and count; ties → lowest index.

When-NOT: need all rows with max → collect list; sorted-row follow-up → binary search / staircase; column-wise max → transpose the aggregate axis.

4. Edge hand-run (K13)

All zeros: best stays 0,0 → [0,0]
Single row [[1,1,0]] → [0,2]
m=1,n=1 [[0]] → [0,0]; [[1]] → [0,1]

5. Interviewer follow-ups

Q1. Why strict > not ≥?
A: ≥ would replace with later equal rows and lose lowest index.

Q2. Complexity unsorted?
A: Θ(m·n) time, Θ(1) extra space.

Q3. Follow-up if rows sorted 0…01…1?
A: Binary search first 1 → count = n−idx; total Θ(m log n).