The K Weakest Rows in a Matrix | February Leetcoding challenge 2021 | Day 15 Manas Sinha
Developer | Designer

The K Weakest Rows in a Matrix

PROBLEM  STATEMENT:
Given a m * n matrix mat of ones (representing soldiers) and zeros (representing civilians), return the indexes of the k weakest rows in the matrix ordered from the weakest to the strongest.
A row i is weaker than row j, if the number of soldiers in row i is less than the number of soldiers in row j, or they have the same number of soldiers but i is less than j. Soldiers are always stand in the frontier of a row, that is, always ones may appear first and then zeros.

Example 1
Input: mat =
[[1,1,0,0,0],
[1,1,1,1,0],
[1,0,0,0,0],
[1,1,0,0,0],
[1,1,1,1,1]],
k = 3
Output: [2,0,3]
Explanation:
The number of soldiers for each row is:
row 0 -> 2
row 1 -> 4
row 2 -> 1
row 3 -> 2
row 4 -> 5
Rows ordered from the weakest to the strongest are [2,0,3,1,4]
Example 2
Input: mat =
[[1,0,0,0],
[1,1,1,1],
[1,0,0,0],
[1,0,0,0]],
k = 2
Output: [0,2]
Explanation:
The number of soldiers for each row is:
row 0 -> 1
row 1 -> 4
row 2 -> 1
row 3 -> 1
Rows ordered from the weakest to the strongest are [0,2,3,1]
Constraints:
• m == mat.length
• n == mat[i].length
• 2 <= n, m <= 100
• 1 <= k <= m
• matrix[i][j] is either 0 or 1.
Sort the matrix row indexes by the number of soldiers and then row indexes.

Explanation

The problem can be solved using a max heap/priority_queue
ALGORITHM:
• Traverse the rows of the matrix.
• Count the number of ones in the row.
• Insert the pair(row-index,count) in the heap.
• Make a custom compare function for the heap so that it keeps the pair with maximum count value on the top and if count is same, it puts the row with greater row number in the top.
• If the heap size exceeds k pop the top element. In this way the heap will have the k element with smallest count value.
• Add the indices to the array and return it.

code

#define pi pair<int,int>
#define mp make_pair

class Solution {
public:
vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
auto mycompare = [](pi a,pi b){
if(a.second == b.second) return a.first < b.first;
return a.second < b.second;
};

priority_queue<pi,vector<pi>,decltype(mycompare)> q(mycompare);

for(int i=0;i<mat.size();++i){
int count = 0;
for(int j : mat[i]){
if(j) count++;
}

q.push(make_pair(i,count));
if(q.size() > k) {

q.pop();
}
}
vector<int> res;
while(!q.empty()){
res.push_back(q.top().first);
q.pop();
}
reverse(res.begin(),res.end());
return res;
}
};