algoadvance

Leetcode 1337. The K Weakest Rows in a Matrix

Problem Statement

You are given an m x n binary matrix mat of 1’s (representing soldiers) and 0’s (representing civilians). The soldiers are positioned in front of the civilians in each row, that is, all the 1’s will appear to the left of all the 0’s in each row.

A row i is weaker than a row j if one of the following is true:

  1. The number of soldiers in row i is less than the number of soldiers in row j.
  2. Both rows have the same number of soldiers, and i is less than j.

Return the indices of the k weakest rows in the matrix ordered from weakest to strongest.

Clarifying Questions

  1. Can a matrix be empty or of minimum size 1x1? For this problem, we assume the matrix is not empty.
  2. Can we assume that the input is always valid and no additional input validation is required? Yes.
  3. What should be the output if k is greater than the number of rows? Assume that k will be valid and less than or equal to the number of rows.

Strategy

To solve this problem:

  1. Calculate the number of soldiers in each row. This can be done by counting the 1’s in each row.
  2. Store each row’s soldier count along with the row index in a vector of pairs.
  3. Sort this vector primarily by soldier count, and secondarily by row index.
  4. Extract the indices of the first k elements from the sorted vector.

Time Complexity

  1. Computing the number of soldiers for each row will take (O(m \cdot n)) time.
  2. Sorting the vector of pairs will take (O(m \log m)) time.
  3. Extracting the first k indices will take (O(k)) time.

Overall, the time complexity will be (O(m \cdot n + m \log m + k)).

Code

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
        int m = mat.size();
        vector<pair<int, int>> soldierCount(m);
        
        // Count the number of soldiers in each row
        for (int i = 0; i < m; ++i) {
            int count = countSoldiers(mat[i]);
            soldierCount[i] = {count, i};
        }
        
        // Sort by number of soldiers and then by row index
        sort(soldierCount.begin(), soldierCount.end());
        
        // Extract the first k indices
        vector<int> result;
        for (int i = 0; i < k; ++i) {
            result.push_back(soldierCount[i].second);
        }
        
        return result;
    }
    
private:
    int countSoldiers(const vector<int>& row) {
        int low = 0, high = row.size();
        while (low < high) {
            int mid = (low + high) / 2;
            if (row[mid] == 1) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
};

Explanation of the Code

  1. Function kWeakestRows: This is the main function that calculates the k weakest rows.
    • We determine the row count m.
    • We initialize a vector of pairs soldierCount where each pair contains the number of soldiers and the row index.
    • We fill this vector by counting the number of soldiers for each row using a helper function countSoldiers.
    • We sort the vector soldierCount.
    • We extract the indices of the k weakest rows from the sorted vector.
  2. Function countSoldiers: This helper function computes the number of soldiers in a given row using binary search.
    • It uses binary search to efficiently count the number of 1s in a sorted row of 1s followed by 0s.

This approach ensures an efficient solution to the problem with balanced time complexity considerations.

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