Update appNew update is available. Click here to update.
Last Updated: Mar 6, 2023

The K Weakest Rows in a Matrix

Author Malay Gain
0 upvotes

Introduction

The K Weakest Rows in a Matrix is a simple problem that can be solved using the brute force approach. A Brute Force Approach or Greedy Approach to a problem is generally the most intuitive solution that can be thought of after looking at the problem. Here we will see how to solve the problem and complexity analysis of our algorithm.

Also See, Hash Function in Data Structure.

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

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

 

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 CodeStudio 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 CodeStudio

Happy learning!

Previous article
Count subsets having distinct even numbers
Next article
Length of the largest subarray with 0 sum
Codekaze-June23 India's Biggest Tech Hiring Challenge is LIVE!
Register Now
Go on top