algoadvance

Leetcode 2643. Row With Maximum Ones

Problem Statement:

You are given a binary matrix (a matrix only containing 0s and 1s) where each row is sorted in non-decreasing order. Your task is to return the index of the row with the maximum number of 1s. If there are multiple rows with the same number of 1s, return the one with the smallest index.

Clarifying Questions:

  1. What should be the return if the matrix has no 1s at all?
    • You would return -1 if no row contains any 1s.
  2. Can the matrix be empty?
    • No, the matrix is guaranteed to have at least one row and one column.
  3. Is there any constraint on the size of the matrix?
    • Constraints might be defined but generally assume reasonable limits for processing time and memory (like hundreds or thousands of elements).

Strategy:

Given that each row is sorted, we can leverage binary search to find the first occurrence of 1 in each row. This approach will help us efficiently determine the number of 1s present in each row.

Steps:

  1. Initialize variables to track the index of the row with the maximum number of 1s and the count of 1s.
  2. Iterate through each row of the matrix, using binary search to find the first 1 in the row.
  3. Calculate the number of 1s in the row by subtracting the index of the first 1 from the total number of columns.
  4. Update the index of the row with the maximum number of 1s if the current row has more 1s.
  5. Return the index of the row with the maximum number of 1s.

Time Complexity:

Code:

#include <vector>
#include <iostream>

using namespace std;

class Solution {
public:
    int rowWithMaxOnes(vector<vector<int>>& mat) {
        int max_row_index = -1;
        int max_ones_count = 0;
        int rows = mat.size();
        int cols = mat[0].size();
    
        for (int i = 0; i < rows; ++i) {
            // Use binary search to find the first 1 in the row
            int first_one_index = findFirstOne(mat[i]);
            if (first_one_index != -1) {
                int ones_count = cols - first_one_index;
                if (ones_count > max_ones_count) {
                    max_ones_count = ones_count;
                    max_row_index = i;
                }
            }
        }
        return max_row_index;
    }
    
    int findFirstOne(vector<int>& row) {
        int left = 0, right = row.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (row[mid] == 1) {
                if (mid == 0 || row[mid - 1] == 0) {
                    return mid;
                } else {
                    right = mid - 1;
                }
            } else {
                left = mid + 1;
            }
        }
        return -1; // No 1s found in the row
    }
};

int main() {
    Solution sol;
    vector<vector<int>> mat = {
        {0, 0, 0, 1},
        {0, 0, 1, 1},
        {0, 1, 1, 1},
        {0, 0, 0, 0}
    };
    
    int index = sol.rowWithMaxOnes(mat);
    cout << "Row with maximum ones is: " << index << endl; // should output 2
    
    return 0;
}

Explanation:

  1. findFirstOne: A helper function that uses binary search to locate the first occurrence of 1 in a given row.
  2. rowWithMaxOnes: Main function that iterates over each row, uses findFirstOne to get the count of 1s in the row, and keeps track of the row with the maximum number of 1s.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI