Binary Search on 2D Arrays: Row with Maximum Number of 1s

Finding the row with the maximum number of $1\text{s}$ in a row-sorted boolean 2D matrix is a classic algorithmic problem. It tests our ability to transition from a naive brute-force linear search to an optimized logarithmic approach by recognizing sorted properties within multidimensional data structures.

1. Problem Statement & Overview

Given an $N \times M$ matrix containing only $0\text{s}$ and $1\text{s}$, where every individual row is sorted in non-decreasing order (all $0\text{s}$ appear before any $1\text{s}$), our goal is to find the index of the row that contains the maximum number of $1\text{s}$.

Edge Rules & Clarifications

• Multiple Rows with Maximum $1\text{s}$: If two or more rows have the exact same maximum count of $1\text{s}$, we must return the row with the smallest index.
• Zero $1\text{s}$ in the Matrix: If the matrix contains no $1\text{s}$ at all (i.e., entirely $0\text{s}$), the algorithm must safely return -1.

2. Core Mental Model & Real-Life Analogy

Real-Life Analogy: Scanning Sorted Attendance Registers

Imagine you are a school administrator looking at $N$ different classrooms, where each classroom has its student attendance records listed in a long ledger row. The students who are present are marked as $1$, and those absent are marked as $0$. Because classrooms are organized such that all absent marks come first followed by present marks, every row is sorted.

Instead of painstakingly checking every single student desk across all rooms (brute-force), you can look at each classroom ledger and immediately pinpoint the exact seat where the first $1$ appears. By subtracting that desk number from the total desk count, you instantly know how many students are present in that room without counting them one by one.

3. Naive Brute-Force Approach

The most straightforward way to solve this problem is to visit every single element in the 2D matrix, count the number of $1\text{s}$ row by row, and keep track of the maximum count encountered so far.

Naive Implementation Walkthrough

1. Initialize maxCount = -1 and rowIndex = -1.
2. Loop through every row from i = 0 to N - 1.
3. Inside each row, loop through every column from j = 0 to M - 1 to sum up the values.
4. If the current row's sum strictly exceeds maxCount, update maxCount and record rowIndex = i. (We use strict inequality > to preserve the lowest index in case of ties).

Complexity Analysis

• Time Complexity: $\mathcal{O}(N \times M)$ because we visit every element in the $N \times M$ grid.
• Space Complexity: $\mathcal{O}(1)$ as no extra data structures are used.

An interviewer will expect an optimization because we are failing to leverage the crucial property given in the problem statement: Every row is sorted.

4. Why Binary Search? (The Optimization Insight)

While we cannot eliminate the outer loop that visits every row ($\mathcal{O}(N)$ traversal), we can optimize how we count the number of $1\text{s}$ in each individual row.

Because each row is sorted (e.g., [0, 0, 1, 1, 1]), finding the number of $1\text{s}$ is equivalent to finding the first occurrence of $1$.

Row elements:  [0,  0,  1,  1,  1]
Indices:        0   1   2   3   4
                             ^
                             First occurrence of 1 is at index 2

If the first $1$ occurs at index idx, and the total column length of the row is M, then the total number of $1\text{s}$ in that row is simply:

Since the row is sorted, finding idx can be accomplished using Binary Search in $\mathcal{O}(\log M)$ time using algorithms like Lower Bound or Upper Bound.

5. Step-by-Step Binary Search Evolution

We can employ any of the standard binary search variants to locate the transition point from $0$ to $1$:

1. Lower Bound of $1$: Finds the first index where the element is $\ge 1$.
2. Upper Bound of $0$: Finds the first index where the element is $> 0$ (which points directly to the first $1$).
3. First Occurrence of $1$: Directly searches for the target value $1$.

Row-by-Row Evaluation Flow

6. Complete Code Implementation

Below is the clean implementation incorporating the binary search optimization for each row.

class Solution {
public:
    // Helper function to find lower bound in a 1D sorted array
    int lowerBound(vector<int>& arr, int n, int x) {
        int low = 0, high = n - 1;
        int ans = n; // Default to n if 1 is not found
        
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] >= x) {
                ans = mid;       // Look on the left for an earlier occurrence
                high = mid - 1;
            } else {
                low = mid + 1;   // Look on the right
            }
        }
        return ans;
    }

    int rowWithMax1s(vector<vector<int>>& matrix) {
        int n = matrix.size();
        int m = matrix[0].size();
        
        int maxCount = 0;
        int index = -1; // Default to -1 if no 1s exist in the matrix
        
        for (int i = 0; i < n; i++) {
            // Find the first occurrence of 1 in the current row
            int firstOneIndex = lowerBound(matrix[i], m, 1);
            
            // Number of 1s is total columns minus the starting index of 1
            int countOnes = m - firstOneIndex;
            
            // Update maxCount and index only if we find a strictly greater count
            if (countOnes > maxCount) {
                maxCount = countOnes;
                index = i;
            }
        }
        
        return index;
    }
};

7. Handling Edge Cases & Practical Pitfalls

1. Matrix Contains Only $0\text{s}$:
   • If a row has no $1\text{s}$ (e.g., [0, 0, 0, 0]), the lowerBound function will return m (the size of the array).
   • The calculated count will be m - m = 0.
   • By initializing maxCount = 0, a count of $0$ will not trigger an update, correctly leaving index = -1 if no $1\text{s}$ exist across the entire matrix.
2. Tie-Breaking Rule:
   • Always use strict inequality (countOnes > maxCount) instead of >=. This ensures that if a subsequent row has the same number of $1\text{s}$ as a previous row, the earlier (smaller) row index is preserved.

8. Complexity Summary

Summary and Key Takeaways

• Exploit Monotonic Properties: Whenever you encounter sorted rows or columns in a 2D matrix, immediately think of Binary Search as a replacement for linear scans.
• Deconstruct 2D into 1D: You cannot optimize the traversal across rows ($\mathcal{O}(N)$), but you can optimize the operation performed inside each row ($\mathcal{O}(\log M)$).
• Lower Bound Utility: Finding the first occurrence of a target element (like $1$) can be efficiently handled using standard lower bound template logic.
• Strict Inequality for Ties: Problems requiring the minimum index upon tie occurrences mandate the use of > rather than >= during comparisons.
• Robust Default States: Initializing maxCount = 0 and index = -1 seamlessly handles edge cases where matrices contain exclusively zero elements.