C++ Online Compiler
Example: Optimized Max Ones Row (Sorted Rows) in C++
C
C++
C#
Java
Python
PHP
main.cpp
STDIN
Run
// 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; }
Output
Clear
ADVERTISEMENTS