1337. The K Weakest Rows in a Matrix
Problem Description
In this problem, we are given a matrix mat
that is composed of binary values - 1
's and 0
's. Every 1
in the matrix represents a soldier, and every 0
represents a civilian. One of the key elements of the setup is the arrangement of the soldiers and civilians in each row; all the soldiers (1's) come before any civilians (0's). This ordering makes it visually similar to a sorted binary array where all 1
's are at the start of the array, followed by all 0
's.
We are asked to evaluate the "strength" of each row based on the number of soldiers (1
's) in it. A row is considered "weaker" if it has fewer soldiers in it than another row, or if it has the same number of soldiers but comes earlier in the matrix (i.e., it has a smaller row index).
The problem requires us to return the indices of the k
weakest rows in the matrix ordered from the weakest to the strongest. It's essentially like constructing a "leaderboard" of rows, with the least number of soldiers making a row rank higher (weaker) on this board.
Intuition
Approaching this problem, we observe two tasks: counting the number of soldiers in each row and then sorting the rows according to their "strength." Since the soldiers (1's) are all positioned to the left, the count of soldiers in a row is equal to the number of continuous 1
's starting from the first column until the first 0
appears. This can be thought of as finding the first occurrence of 0
in the row.
Since the rows are sorted in the non-increasing order with all the soldiers at the beginning, we can use a binary search technique to quickly find the position of the first civilian (0
) which indicates the number of soldiers in the row. The binary search here drastically reduces the time complexity over a linear scan, especially when the rows are long.
We construct a result ans
that maps each row to the number of soldiers it has, by applying the binary search on the reversed row. We reverse the row before applying the binary search with bisect_right
because this function is typically used to find the insertion point in a sorted array to maintain the order. By reversing, our soldiers 1
come at the end, and the insertion point for 0
tells us the number of 1
's.
After we have the counts for each row, we create an index list idx
which initially is just a list of row indices [0, 1, 2, ..., m-1]
. We sort this index list based on the corresponding soldier counts from the ans
array. Finally, we use slicing to get the first k
elements from this sorted index list which represent the indices of the k
weakest rows.
Learn more about Binary Search, Sorting and Heap (Priority Queue) patterns.
Solution Approach
The solution makes effective use of Python's built-in bisect
library, which provides support for maintaining a list in sorted order without having to sort the list after each insertion. In particular, the bisect_right
function is utilized to implement a binary search through a row to find the count of soldiers in that row.
Here's a step-by-step breakdown of the solution:
- Determine the dimensions of the matrix with
m
as the number of rows andn
as the number of columns. - An array
ans
is created to hold the number of soldiers (1's) for each row. - We iterate over each row in the matrix, and for each row, we apply
bisect_right
to the reversed row:bisect_right(row[::-1], 0)
. This reversed row is a trick used to turn our sorted array of 1's followed by 0's into an array where a binary search can find the insertion point of 0 effectively. The result of this operation is the count of civilians (0's) in the reversed row, which is subtracted fromn
to get the count of soldiers. - Create an index list
idx
containing the indices of the rows, which starts from 0 up tom-1
. - The index list
idx
is then sorted using a lambda function as the key. This lambda function maps each indexi
to the number of soldiersans[i]
, ensuring the sort operation arranges the indices according to the strength of the rows (with ties broken by row index, as per problem statement). - We use list slicing to retrieve the first
k
indices from the sortedidx
, giving us the indices of thek
weakest rows.
Code Snippet Deconstructed
Let's look at the critical sections of the code:
-
ans = [n - bisect_right(row[::-1], 0) for row in mat]
This line computes the strength of each row and stores it inans
. It calculates the number of soldiers as the total lengthn
minus the number of civilians at the end of each reversed row. -
idx.sort(key=lambda i: ans[i])
This line sorts theidx
list according to the number of soldiers in each corresponding row. The lambda function returns the number of soldiers for each row usingans[i]
as the key, ensuring that rows with fewer soldiers come first. -
return idx[:k]
Returns the firstk
elements from the sorted list of indices, which corresponds to thek
weakest rows in the matrix ordered from weakest to strongest.
In terms of algorithms and data structures, this solution primarily uses the binary search algorithm (through bisect_right
) and basic list operations in Python (list comprehension, sorting, and slicing).
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a matrix mat
and an integer k
:
mat = [ [1, 1, 0, 0], [1, 1, 1, 0], [1, 0, 0, 0], [1, 1, 0, 0], [1, 1, 1, 1] ] k = 3
In this matrix:
- Row 0 has 2 soldiers.
- Row 1 has 3 soldiers.
- Row 2 has 1 soldier (making it the weakest).
- Row 3 has 2 soldiers.
- Row 4 has 4 soldiers (making it the strongest).
We need to find the indices of the k
weakest rows in the matrix, which are k = 3
in our example.
Following the solution approach:
- The dimensions of the matrix are
m = 5
rows andn = 4
columns. - We'll create an array
ans
to hold counts of soldiers for each row.
For each row's count of soldiers using bisect_right
:
ans[0] = 4 - bisect_right([0, 0, 1, 1][::-1], 0) = 4 - 2 = 2
ans[1] = 4 - bisect_right([0, 1, 1, 1][::-1], 0) = 4 - 3 = 1
ans[2] = 4 - bisect_right([0, 0, 0, 1][::-1], 0) = 4 - 1 = 3
ans[3] = 4 - bisect_right([0, 0, 1, 1][::-1], 0) = 4 - 2 = 2
ans[4] = 4 - bisect_right([1, 1, 1, 1][::-1], 0) = 4 - 4 = 0
After applying the count for each row, ans
looks like this: [2, 1, 3, 2, 0]
.
-
Now we have
ans = [2, 1, 3, 2, 0]
and our index listidx = [0, 1, 2, 3, 4]
. -
Sorting the index list
idx
using theans
array:
After sorting idx
based on ans
values, we get the order [4, 1, 0, 3, 2]
since ans[4]
corresponds to the strongest row and ans[2]
corresponds to the weakest.
- Since we want the
k
weakest rows, we take the firstk
elements of the sorted indexidx
list:[4, 1, 0]
.
The array [4, 1, 0]
is then sorted to maintain the row order: [0, 1, 4]
.
- The final answer, which represents the indices of the
k
weakest rows ordered from weakest to stronger, is[0, 1, 4]
.
This method allows for efficiently determining the weakest rows due to the use of the bisect_right
to perform binary searches, rather than linear searches, and thus reduces the average complexity of the solution.
Solution Implementation
1from typing import List
2from bisect import bisect_right
3
4class Solution:
5 def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
6
7 # Determine the dimensions of the matrix
8 num_rows = len(mat)
9 num_cols = len(mat[0])
10
11 # Calculate the soldier count in each row. Since rows are sorted, the count of 1s is found by
12 # subtracting the first position of a 0 from the end of the reversed row, from the row width.
13 soldier_counts = [num_cols - bisect_right(row[::-1], 0) for row in mat]
14
15 # Create a list of indices from 0 to the number of rows - 1.
16 indices = list(range(num_rows))
17
18 # Sort the indices based on the number of soldiers in the row, using the soldier_counts as keys.
19 indices.sort(key=lambda i: soldier_counts[i])
20
21 # Slice the list of indices to return only the first 'k' elements, corresponding to the k weakest rows.
22 return indices[:k]
23
1import java.util.ArrayList;
2import java.util.Comparator;
3import java.util.List;
4
5class Solution {
6 public int[] kWeakestRows(int[][] mat, int k) {
7 int rowCount = mat.length; // Number of rows in the matrix
8 int colCount = mat[0].length; // Number of columns in the matrix
9 int[] soldierCount = new int[rowCount]; // Array to store the count of soldiers in each row
10 List<Integer> indices = new ArrayList<>(); // List to store the indices of the rows
11
12 // Populate the list with indices and the soldierCount array with the number of soldiers in each row
13 for (int i = 0; i < rowCount; ++i) {
14 indices.add(i);
15 int left = 0, right = colCount;
16 // Use binary search to find the number of soldiers in the row
17 while (left < right) {
18 int mid = (left + right) >> 1; // Find the middle index
19 if (mat[i][mid] == 0) { // If mid element is 0, search in the left half
20 right = mid;
21 } else { // Else search in the right half
22 left = mid + 1;
23 }
24 }
25 soldierCount[i] = left; // Store the soldier count (index of the first 0)
26 }
27
28 // Sort the indices based on the number of soldiers (strength of the row)
29 indices.sort(Comparator.comparingInt(i -> soldierCount[i]));
30
31 int[] weakestRows = new int[k]; // Array to store the k weakest rows
32 // Fill the weakestRows array with the first k indices from the sorted list
33 for (int i = 0; i < k; ++i) {
34 weakestRows[i] = indices.get(i);
35 }
36 return weakestRows; // Return the result
37 }
38}
39
1#include <vector>
2#include <algorithm>
3using namespace std;
4
5class Solution {
6public:
7 // Helper function to find the number of soldiers in the row.
8 // Soldiers are represented by 1s and are always to the left of civilians (0s).
9 int countSoldiers(vector<int>& row) {
10 int left = 0;
11 int right = row.size() - 1;
12 while (left <= right) {
13 int mid = left + (right - left) / 2;
14 if (row[mid] == 0)
15 right = mid - 1; // No soldier at the mid, look left.
16 else
17 left = mid + 1; // Soldier found, look right.
18 }
19 return left; // left will point to the first civilian (0), which is equal to the soldier count.
20 }
21
22 // Function to find the k weakest rows in the matrix.
23 vector<int> kWeakestRows(vector<vector<int>>& matrix, int k) {
24 vector<pair<int, int>> strengthIndexPairs; // Pairs of soldier count and original row index.
25 vector<int> weakestRows; // Vector to store indices of the k weakest rows.
26
27 // Compute the soldier count for each row and store along with the row index.
28 for (int i = 0; i < matrix.size(); i++) {
29 int soldierCount = countSoldiers(matrix[i]);
30 strengthIndexPairs.push_back({soldierCount, i});
31 }
32
33 // Sort the pairs by the number of soldiers and use the index for tie-breaking.
34 sort(strengthIndexPairs.begin(), strengthIndexPairs.end());
35
36 // Collect the indices of the k weakest rows.
37 for (int i = 0; i < k; i++) {
38 weakestRows.push_back(strengthIndexPairs[i].second);
39 }
40
41 return weakestRows; // Return the result.
42 }
43};
44
1function kWeakestRows(mat: number[][], k: number): number[] {
2 let rowCount = mat.length;
3
4 // Create a map of sums of the rows along with their original indices
5 let rowCountSumMap = mat.map((row, index) => [row.reduce((accumulator, currentValue) => accumulator + currentValue, 0), index]);
6
7 let weakestRows = []; // This array will store the indices of the k weakest rows
8
9 // Perform a modified bubble sort to find the k weakest rows. Note: this sorting is not the most efficient method for large datasets.
10 for (let i = 0; i < k; i++) {
11 for (let j = i + 1; j < rowCount; j++) { // Start with j = i + 1 as we already have i in position
12 // Compare row sum, and then index if sums are equal
13 if (
14 rowCountSumMap[j][0] < rowCountSumMap[i][0] ||
15 (rowCountSumMap[j][0] === rowCountSumMap[i][0] && rowCountSumMap[j][1] < rowCountSumMap[i][1])
16 ) {
17 // Swap with destructuring if current row is 'weaker' or has a smaller index than i-th
18 [rowCountSumMap[i], rowCountSumMap[j]] = [rowCountSumMap[j], rowCountSumMap[i]];
19 }
20 }
21 // Add the index of the i-th weakest row to our answer
22 weakestRows.push(rowCountSumMap[i][1]);
23 }
24
25 return weakestRows; // Return the k weakest rows' indices
26}
27
Time and Space Complexity
The time complexity of the code primarily consists of two parts: the computation of the soldiers in each row and the sorting of the index based on the number of soldiers.
-
Computing the number of soldiers in each row: This uses a binary search (
bisect_right
) for each of them
rows. Since the binary search operates on a row of sizen
, the complexity for this part isO(m * log(n))
. -
Sorting the index list: After having computed the number of soldiers, we sort
m
indices based on the computed values. The worst-case time complexity for sorting in Python isO(m * log(m))
.
Combining both parts, the total time complexity is O(m * log(n) + m * log(m))
.
In terms of space complexity:
- The
ans
list isO(m)
because it contains the number of soldiers for each of them
rows. - The
idx
list is alsoO(m)
because it includes an index for each row. - No additional significant space is used.
Hence, the space complexity is O(m)
as we only need space proportional to the number of rows.
Learn more about how to find time and space complexity quickly using problem constraints.
The three-steps of Depth First Search are:
- Identify states;
- Draw the state-space tree;
- DFS on the state-space tree.
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue
Want a Structured Path to Master System Design Too? Donāt Miss This!