Find the row with maximum 1's matrix

Problem#

Given a boolean 2D array, where each row is sorted.
Find the row with the maximum number of 1s.

Input and Output#

Test Case

Case 1

Solutions#

Naive Approach#

A simple method is to do a row-wise traversal of the matrix, count the number of 1s in each row, and compare the count with max. Finally, return the index of the row with maximum 1s.

C++

#include <iostream>
#include <vector>

using namespace std;

int rowWithMax1s(vector<vector<int>> mat) {
  int rowIndex = -1;
  int maxCount = 0;
  for (int i = 0; i < mat.size(); i++) {
    int count = 0;
    for (int j = 0; j < mat[i].size(); j++) {
      if (mat[i][j] == 1) count++;
    }
    if (count > maxCount) {
      maxCount = count;
      rowIndex = i;
    }
  }
  return rowIndex;
}

int main() {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> mat(n, vector<int>(m, 0));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) cin >> mat[i][j];
  }
  cout << rowWithMax1s(mat);
  return 0;
}

Time Complexity: \(O(m*n)\)
Space Complexity: \(O(1)\)
\(m\) - no of columns of matrix
\(n\) - no of rows of matrix

Binary Search#

We can do better. Since each row is sorted, we can use Binary Search to count of 1s in each row. We find the index of first instance of 1 in each row. The count of 1s will be equal to total number of columns minus the index of first 1.

C++

#include <iostream>
#include <vector>

using namespace std;

int binarySearch(vector<int>& arr, int low, int high) {
  if (high >= low) {
    int mid = low + (high - low) / 2;
    if ((mid == 0 || arr[mid - 1] == 0) && arr[mid] == 1) return mid;
    else if (arr[mid] == 0)
      return binarySearch(arr, (mid + 1), high);
    else
      return binarySearch(arr, low, (mid - 1));
  }
  return -1;
}

int rowWithMax1s(vector<vector<int>>& mat) {
  int max_row_index = 0, max = -1;
  int i, index;
  for (i = 0; i < mat.size(); i++) {
    // do binary search
    index = binarySearch(mat[i], 0, mat[i].size() - 1);
    if (index != -1 && mat[i].size() - index > max) {
      max = mat[i].size() - index;
      max_row_index = i;
    }
  }
  return max_row_index;
}

int main() {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> mat(n, vector<int>(m, 0));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) cin >> mat[i][j];
  }
  cout << rowWithMax1s(mat);
  return 0;
}

Time Complexity: \(O(m \log n)\) where m is number of rows and n is number of columns in matrix.
Auxiliary Space: \(O(\log n)\), as implicit stack is created due to recursion.
\(m\) - no of columns of matrix
\(n\) - no of rows of matrix

Linear Search only on some rows#

The above solution can be optimized further. Instead of doing binary search in every row, we first check whether the row has more 1s than max so far. If the row has more 1s, then only count 1s in the row. Also, to count 1s in a row, we don’t do binary search in complete row, we do search in before the index of last max.

C++

#include <iostream>
#include <vector>

using namespace std;

int rowWithMax1s(vector<vector<int>> mat) {
  int j, max_row_index = 0;
  j = mat[0].size() - 1;

  for (int i = 0; i < mat.size(); i++) {
    bool flag = false; // to check whether a row has more 1's than previous
    while (j >= 0 && mat[i][j] == 1) {
      j--;
      flag = true;
    }
    if (flag) max_row_index = i;
  }
  if (max_row_index == 0 && mat[0][mat[0].size() - 1] == 0) return -1;
  return max_row_index;
}

int main() {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> mat(n, vector<int>(m, 0));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) cin >> mat[i][j];
  }
  cout << rowWithMax1s(mat);
  return 0;
}

Time Complexity: \(O(m+n)\) where m is number of rows and n is number of columns in matrix.
Auxiliary Space: \(O(1)\), as implicit stack is created due to recursion.
\(m\) - no of columns of matrix
\(n\) - no of rows of matrix

Last update: 2023-10-05
Created: 2023-10-05