Approach
We will solve this problem by applying the brute force approach with the help of a hashmap.
 At first, we will calculate the power of each row and store it in a hash map along with the row index as {power, index} (i.e., keyvalue pair). We will implement the map using the vector of pairs ( in C++).

Sort the hashmap based on the value of the power of the corresponding rows. By default, the C++ STL sort() function sorts the vector of pairs based on the first element of the pairs.
 Then first k row indices stored in the hash table are the K weakest rows. We will store them separately for returning the required output.
vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
vector<pair<int,int>> mp;
for(int i=0;i<mat.size();i++)
{
int soldiers=0;
// calculating the power of each row
for(int j=0;j<mat[0].size();j++)
{
if(mat[i][j]==1)
{
soldiers++;
}
}
// storing {power, index} as keyvalue pair
mp.push_back({soldiers,i});
}
// sorting the hash map based on value of power of the rows.
sort(mp.begin(),mp.end());
vector<int> ans;
// storing the weakest rows
for(int i=0;i<k;i++)
{
//storing the row index weakest to strongest
ans.push_back(mp[i].second);
}
return ans;
}
You can also try this code with Online C++ Compiler
Run Code
Code
// c++ code for finding K Weakest Rows in a Matrix
#include<bits/stdc++.h>
using namespace std;
vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
vector<pair<int,int>> mp;
for(int i=0;i<mat.size();i++)
{
int soldiers=0;
// calculating the power of each row
for(int j=0;j<mat[0].size();j++)
{
if(mat[i][j]==1)
{
soldiers++;
}
}
// storing {power, index} as keyvalue pair
mp.push_back({soldiers,i});
}
//sorting on the basis of number of soldiers i.e. first element
//of the pair
sort(mp.begin(),mp.end());
vector<int> ans;
for(int i=0;i<k;i++)
{
//storing the row numbers weakest to strongest
ans.push_back(mp[i].second);
}
return ans;
}
// driver code
int main()
{
vector<vector<int>> 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}};
int k=3;
vector<int> ans=kWeakestRows(mat,k);
for(int i=0;i<k;i++)
{
cout<<ans[i]<<" ";
}
}
You can also try this code with Online C++ Compiler
Run Code
Output
4,0,2,1
You can also read about the Longest Consecutive Sequence.
Complexity Analysis
Time Complexity
The time complexity of the above implementation is O(m*n) where m is the number of rows and n is the number of columns of the given matrix.
Space Complexity
Space complexity is O(m) as we are using extra space here.
Frequently Asked Questions
What is a hash map?
It is a special kind of data structure that is used to store a unique key and associated value(keyvalue pair).
What kind of sorting is used in the C++ STL sort() function?
It uses a hybrid sorting algorithm of insertion sort, heap sort, and quicksort.
Conclusion
This article covered how to solve the problem of K Weakest Rows in a Matrix and its c++ code.
We strongly recommend you check out the Coding Ninjas Studio library for getting a better hold of the data structures and algorithms.
Recommended Problems
Recommended Articles
Check out some of the amazing Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Basics of Java, etc. along with some Contests and Interview Experiences only on Coding Ninjas Studio.
Happy learning!