The K Weakest Rows in a Matrix

Malay Gain
Last Updated: Jun 24, 2022

Introduction

The K Weakest Rows in a Matrix is a simple problem that can be solved using the brute force approach. Here we will see how to solve the problem and complexity analysis of our algorithm.

Problem Statement

For a given (m x n) matrix 'mat' of 1's ( which represents soldiers) and 0's (which represents civilians) where all the 1's will appear to the left of all the 0's in each row such that the soldiers are standing in front of the civilians.

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

  • The number of soldiers in the i-th row is less than the number of soldiers in row j.
  • Both rows have the same number of soldiers, and i < j.

You need to find k weakest rows from the matrix based on the given conditions.

Input: mat = 

[[1,1,1,0,0],

 [1,1,1,1,0],

 [1,1,1,0,0],

 [1,1,1,1,1],

 [1,0,0,0,0]], 

k = 4

Output: [4,0,2,1,3]

 

Explanation: 

1

1

1

0

0

1

1

1

1

0

1

1

1

0

0

1

1

1

1

1

1

0

0

0

0

 

1  represents soldier

0  represents civilian

In each row the number of soldiers is: 

0th row -> 3 

1th row -> 4

2nd row -> 3

3rd row -> 5

4th row -> 1


The order of rows from weakest to strongest is [4,0,2,1,3] (row indices).

Note: Please try to solve the problem first and then see the below solution approach.

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 hash map 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;
   }
    

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]<<" ";
}

}

Output

4,0,2,1

 

Complexity Analysis

Time Complexity

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 to check out the CodeStudio library for getting a better hold of the data structures and algorithms.

Apart from this, you can practice a wide range of coding questions commonly asked in interviews in CodeStudio. Along with coding questions, we can also find the interview experience of scholars working in renowned product-based companies here. 

Happy learning!

 

Was this article helpful ?
0 upvotes