Example: Optimized Max Ones Row (Sorted Rows) in C++

// Optimized Max Ones Row (Sorted Rows)
    #include <iostream>
    #include <vector>

    using namespace std;

    // Function to find the row with maximum 1s using an optimized two-pointer approach
    // Assumes rows are sorted (all 0s followed by all 1s)
    int findMaxOnesRowOptimized(const vector<vector<int>>& matrix) {
        int rows = matrix.size();
        if (rows == 0) {
            return -1; // Handle empty matrix
        }
        int cols = matrix[0].size();
        if (cols == 0) {
            return -1; // Handle empty rows
        }

        int maxOnesRowIndex = -1;
        int j = cols - 1; // Start from the last column (rightmost)

        // Step 1: Find the first column where a 0 can exist for the first row
        // This effectively finds the first 1 in the first row, or sets j to -1 if all are 0s.
        // Or points to the column index of the first 1 encountered.
        while (j >= 0 && matrix[0][j] == 1) {
            maxOnesRowIndex = 0; // If row 0 has 1s, it's a candidate
            j--;
        }

        // Step 2: Iterate through the remaining rows from the second row
        for (int i = 1; i < rows; ++i) {
            // While current row has 1s at column j or to its right
            // and we haven't gone out of bounds to the left
            while (j >= 0 && matrix[i][j] == 1) {
                maxOnesRowIndex = i; // This row has at least as many 1s as previous candidates, potentially more
                j--; // Move left to find more 1s in this row
            }
        }
        return maxOnesRowIndex;
    }

    int main() {
        // Example Matrix 1 (sorted rows)
        vector<vector<int>> matrix1 = {
            {0, 0, 1, 1},
            {0, 1, 1, 1},
            {0, 0, 0, 1},
            {0, 0, 0, 0}
        };

        // Example Matrix 2 (another sorted matrix)
        vector<vector<int>> matrix2 = {
            {1, 1, 1},
            {0, 0, 0},
            {0, 1, 1}
        };

        // Example Matrix 3 (all zeros)
        vector<vector<int>> matrix3 = {
            {0, 0, 0},
            {0, 0, 0},
            {0, 0, 0}
        };

        // Step 1: Test with matrix1
        cout << "Matrix 1 (Sorted Rows):" << endl;
        for (const auto& row : matrix1) {
            for (int val : row) {
                cout << val << " ";
            }
            cout << endl;
        }
        cout << "Row with max 1s (Optimized): " << findMaxOnesRowOptimized(matrix1) << endl << endl;

        // Step 2: Test with matrix2
        cout << "Matrix 2 (Sorted Rows):" << endl;
        for (const auto& row : matrix2) {
            for (int val : row) {
                cout << val << " ";
            }
            cout << endl;
        }
        cout << "Row with max 1s (Optimized): " << findMaxOnesRowOptimized(matrix2) << endl << endl;

        // Step 3: Test with matrix3
        cout << "Matrix 3 (Sorted Rows):" << endl;
        for (const auto& row : matrix3) {
            for (int val : row) {
                cout << val << " ";
            }
            cout << endl;
        }
        cout << "Row with max 1s (Optimized): " << findMaxOnesRowOptimized(matrix3) << endl << endl;


        return 0;
    }