Find row with maximum no. of 1s

Problem Statement

Given a binary matrix (containing only 0s and 1s) where each row is sorted in non-decreasing order (all 0s come before all 1s), find the row with the maximum number of 1s.

Example:

• Input: matrix = [[0, 0, 0, 1], [0, 1, 1, 1], [1, 1, 1, 1], [0, 0, 0, 0]]
• Output: 2 (0-indexed)
• Explanation: Row 2 has the maximum 1s (4 ones)

Approach 1: Brute Force (Count 1s in Each Row)

Intuition

Count the number of 1s in each row and keep track of the row with maximum count.

Algorithm

1. For each row, count the number of 1s
2. Keep track of the maximum count and corresponding row index
3. Return the row index with maximum 1s

public class Solution {
    public int rowWithMax1sBrute(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int maxCount = 0, maxRow = -1;
        
        for (int i = 0; i < m; i++) {
            int count = 0;
            for (int j = 0; j < n; j++) {
                count += matrix[i][j];
            }
            if (count > maxCount) {
                maxCount = count;
                maxRow = i;
            }
        }
        
        return maxRow;
    }
}

Complexity Analysis

• Time Complexity: O(m*n) - Traverse entire matrix
• Space Complexity: O(1) - Only using constant extra space

Approach 2: Binary Search (Better)

Intuition

Since each row is sorted (0s followed by 1s), we can use binary search to find the first occurrence of 1 in each row. The number of 1s = n - (index of first 1).

Algorithm

1. For each row, use binary search to find the first 1
2. Count of 1s = n - firstOneIndex
3. Track the row with maximum count

public class Solution {
    private int firstOneIndex(int[] row) {
        int left = 0, right = row.length - 1;
        int result = row.length;  // Default: no 1s found
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (row[mid] == 1) {
                result = mid;
                right = mid - 1;  // Look for earlier 1
            } else {
                left = mid + 1;
            }
        }
        
        return result;
    }
    
    public int rowWithMax1sBinary(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int maxCount = 0, maxRow = -1;
        
        for (int i = 0; i < m; i++) {
            int firstOne = firstOneIndex(matrix[i]);
            int count = n - firstOne;
            
            if (count > maxCount) {
                maxCount = count;
                maxRow = i;
            }
        }
        
        return maxRow;
    }
}

Complexity Analysis

• Time Complexity: O(m * log n) - Binary search on each of m rows
• Space Complexity: O(1) - Only using constant extra space

Approach 3: Staircase Traversal (Optimal)

Intuition

Start from the top-right corner. Move left while we see 1s (to find more 1s). Move down when we see 0 (this row can't have more 1s than current best).

Algorithm

1. Start from top-right corner (row = 0, col = n-1)
2. While within bounds:
   • If current element is 1, move left and update answer row
   • If current element is 0, move down (this row has fewer 1s)
3. Return the row index with maximum 1s

public class Solution {
    public int rowWithMax1s(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int maxRow = -1;
        int col = n - 1;  // Start from rightmost column
        
        for (int row = 0; row < m; row++) {
            // Move left while we see 1s
            while (col >= 0 && matrix[row][col] == 1) {
                col--;
                maxRow = row;  // Update answer
            }
        }
        
        return maxRow;
    }
}

Complexity Analysis

• Time Complexity: O(m + n) - At most m + n steps
• Space Complexity: O(1) - Only using constant extra space

Why Staircase Works

The key insight: We never need to look at columns to the right of our current position because we've already found a row with that many 1s.

Key Takeaways

1. Staircase traversal achieves O(m + n) by leveraging sorted property
2. Once we find a 1 in column j, no need to check columns > j for subsequent rows
3. The column pointer only moves left (never right), ensuring O(m + n)
4. Binary search approach is also efficient at O(m * log n)
5. Similar technique works for finding row with maximum 0s (traverse from left)
6. This pattern is useful for other sorted binary matrix problems