## 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!**