You are given an m x n binary matrix mat of 1's (representing soldiers) and 0's (representing civilians). The soldiers are positioned in front of the civilians. That is, all the 1's will appear to the left of all the 0's in each row.
A row i is weaker than a row j if one of the following is true:
i is less than the number of soldiers in row j.i < j.Return the indices of the k weakest rows in the matrix ordered from weakest to strongest.
Example 1:
Input: 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]], k = 3 Output: [2,0,3] Explanation: The number of soldiers in each row is: - Row 0: 2 - Row 1: 4 - Row 2: 1 - Row 3: 2 - Row 4: 5 The rows ordered from weakest to strongest are [2,0,3,1,4].
Example 2:
Input: mat = [[1,0,0,0], [1,1,1,1], [1,0,0,0], [1,0,0,0]], k = 2 Output: [0,2] Explanation: The number of soldiers in each row is: - Row 0: 1 - Row 1: 4 - Row 2: 1 - Row 3: 1 The rows ordered from weakest to strongest are [0,2,3,1].
Constraints:
m == mat.lengthn == mat[i].length2 <= n, m <= 1001 <= k <= mmatrix[i][j] is either 0 or 1.In this approach, we directly count the number of soldiers in each row by iterating through the elements of the row, and then sort the rows based on the count followed by their index to determine the order.
Steps to implement:
The C solution involves using a two-dimensional array to track the number of soldiers and their respective row indices. We then use the quicksort function with a custom comparator to sort this array by soldiers' count first and indices as a tiebreaker. Finally, extract the indices of the weakest rows.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m*n + m*log m) due to counting and sorting the rows.
Space Complexity: O(m) to store the row strength information.
This approach uses binary search to efficiently count the number of soldiers in each row. Given that soldiers are always positioned before civilians, binary search can help quickly find the first civilian and thus the count of soldiers.
Implementation steps:
This solution optimizes soldier count using binary search in each row. This reduces the time complexity to efficiently find each row's strength before sorting and extracting indices.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m*log n + m*log m) due to binary search for counting and sorting rows.
Space Complexity: O(m), for maintaining strength array storage.
| Approach | Complexity |
|---|---|
| Approach 1: Simple Counting and Sorting | Time Complexity: O(m*n + m*log m) due to counting and sorting the rows. Space Complexity: O(m) to store the row strength information. |
| Approach 2: Binary Search for Counting | Time Complexity: O(m*log n + m*log m) due to binary search for counting and sorting rows. Space Complexity: O(m), for maintaining strength array storage. |
The K Weakest Rows in a Matrix | Live Coding with Explanation | Leetcode - 1337 • Algorithms Made Easy • 10,150 views views
Watch 9 more video solutions →Practice The K Weakest Rows in a Matrix with our built-in code editor and test cases.
Practice on FleetCode