The K Weakest Rows in a Matrix

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., key-value 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 key-value 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 key-value 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(key-value 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

• Reset Matrix
• Sorted Matrix
• Unique Matrix

Recommended Articles

• Types of Matrices
• Sort the matrix row-wise and column-wise
• Top Array Problems

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!