Table of Contents
Problem statement
In the problem ” The K Weakest Rows in a Matrix” we are given a matrix of n rows and m columns. matrix is filled with 0 or 1. The special thing about this matrix is that all the ones are towards the left-hand side of each row and all the zeroes are towards the right-hand side.
There are a set of rules to measure the strength of each row.
- The row with more numbers of ones has greater strength.
- If the tie occurs then the row with a smaller row number has less strength.
The problem asks to find the k weakest rows in a matrix.
Example
grid = [[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]], k = 3
[2,0,3]
Explanation:
- Zeroth row ->2
- First row->4
- Second row->1
- Third row->2
- Fourth row->5
Between the zeroth and fourth row, the fourth is stronger. So the rows arranged from weakest to strongest:2,0,3,1,4.
The approach of The K Weakest Rows in a Matrix Leetcode Solution
To understand the approach better let us use the same example for better understanding. Count the number of ones in each row. But when we will do this by traversing the complete row it will take linear time. So to improve the time complexity we will use binary search to find the index of the first zero in each row and that index will be the number of ones in each row.
We want to do sorting according to two conditions:
- The number of ones in each row.
- If the number of ones are equal then row number.
We can convert it to one variable using this trick. we can create a score to match the sort condition from the description.
score = soldiersCount * rows + currentRowIndex
So we can get soldiersCount by score/rows, and get rowIndex by score % rows.
Now we will sort the score and the index of the starting k score will be the answer.
Implementation
C++ code for The K Weakest Rows in a Matrix
#include <bits/stdc++.h>
using namespace std;
int numOnes( vector<int> row) {
int lo = 0;
int hi = row.size();
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (row[mid] == 1)
lo = mid + 1;
else
hi = mid;
}
return lo;
}
vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
int rows = mat.size();
int cols = mat[0].size();
int score[rows];
int j;
for (int i = 0; i < rows; i++) {
j = numOnes(mat[i]);
score[i] = j * rows + i;
}
sort(score,score+rows);
vector<int>ans(k);
for (int i = 0; i < k; i++) {
ans[i] = score[i] % rows;
}
return ans;
}
int main()
{
vector<vector<int> > arr = { {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(arr,k);
for(int i=0;i<k;i++)
cout<<ans[i]<<" ";
cout<<endl;
return 0;
}
2 0 3
Java code for The K Weakest Rows in a Matrix
import java.util.*;
public class Tutorialcup {
public static int numOnes(int[] row) {
int lo = 0;
int hi = row.length;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (row[mid] == 1)
lo = mid + 1;
else
hi = mid;
}
return lo;
}
public static int[] kWeakestRows(int[][] mat, int k) {
int rows = mat.length;
int cols = mat[0].length;
int[] score = new int[rows];
int j;
for (int i = 0; i < rows; i++) {
j = numOnes(mat[i]);
score[i] = j * rows + i;
}
Arrays.sort(score);
for (int i = 0; i < k; i++) {
score[i] = score[i] % rows;
}
return Arrays.copyOfRange(score, 0, k);
}
public static void main(String[] args) {
int [][] arr ={ {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;
int[]ans=kWeakestRows(arr,k);
System.out.println(Arrays.toString(ans));
}
}2 0 3
Complexity Analysis of The K Weakest Rows in a Matrix Leetcode Solution
Time complexity
The time complexity of the above code is O(n*logm+nlogn). n*logm is for calculating the number of ones in each row and n*logn is for sorting. Here n is the numbers of rows and m is number of columns.
Space complexity
The space complexity of the above code is O(n) because we are storing the score. Here n is the number of rows in the matrix.