#1337

Easy

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

The K Weakest Rows in a Matrix

Find the k weakest rows in a binary matrix where rows contain soldiers and civilians, using sorting and binary search techniques.

array binary search sorting heap priority queue matrix

Problem Statement

You are given an m x n binary matrix 'mat' where each element represents either a soldier (1) or a civilian (0). The soldiers always appear to the left of civilians in each row. Your task is to identify the k weakest rows in the matrix. A row is considered weaker if it has fewer soldiers, with ties broken by row index.

Return the indices of the k weakest rows in the matrix, ordered from weakest to strongest. The solution must make use of sorting and binary search to efficiently identify the rows based on the number of soldiers in each row.

Examples

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]

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]

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.length
n == mat[i].length
2 <= n, m <= 100
1 <= k <= m
matrix[i][j] is either 0 or 1.

Solution Approach

Count Soldiers Using Binary Search

Since soldiers are always positioned to the left of civilians in each row, a binary search can be applied to count the number of soldiers in each row. This method avoids unnecessary traversal of the entire row, improving efficiency.

Sort by Number of Soldiers

After counting the soldiers, sort the rows by their soldier count. In case of ties (equal number of soldiers), rows should be sorted by their index in the original matrix.

Select the k Weakest Rows

Once the rows are sorted by the number of soldiers (and row index for tie-breaking), extract the indices of the k weakest rows to form the final output.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity primarily depends on the sorting step, which is O(m log m), where m is the number of rows. Binary search over each row adds an O(log n) factor, making the overall complexity O(m log m + m log n). The space complexity is O(m) for storing row information during sorting.

What Interviewers Usually Probe

Check if the candidate efficiently applies binary search to count soldiers in each row.
Evaluate how the candidate handles sorting and tie-breaking when soldier counts are equal.
Assess the candidate's ability to optimize for both time and space complexity within the problem's constraints.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the requirement for sorting rows based on both soldier count and row index in case of ties.
Using a brute-force approach to count soldiers in each row instead of binary search, leading to inefficiency.
Not properly handling edge cases, such as when multiple rows have the same number of soldiers.

Follow-up variants

Handling larger matrices where time and space complexity become more significant.
Modifying the problem to return the indices of the k strongest rows instead of the weakest.
Allowing for different sorting criteria, such as sorting by the number of civilians instead of soldiers.

FAQ

What is the primary algorithmic approach for this problem?

The primary approach is to use binary search to count soldiers in each row and then sort the rows based on soldier count and index.

How does sorting affect the time complexity of the solution?

Sorting the rows by soldier count and index contributes to an O(m log m) time complexity, where m is the number of rows in the matrix.

What is the significance of using binary search in this problem?

Binary search is used to count soldiers efficiently by exploiting the sorted nature of each row, reducing the need to scan each row completely.

Can the solution be optimized further for larger matrices?

While the current approach is optimal in terms of time complexity for this problem, further optimizations may be explored based on the matrix size and constraints.

What happens if multiple rows have the same number of soldiers?

In the case of a tie, the rows are ordered by their index in the matrix, ensuring a stable and deterministic output.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

class Solution:
    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
        m, n = len(mat), len(mat[0])
        ans = [n - bisect_right(row[::-1], 0) for row in mat]
        idx = list(range(m))
        idx.sort(key=lambda i: ans[i])
        return idx[:k]

Continue Practicing

#378 kth smallest element in a sorted matrix #1268 search suggestions system #1439 find the kth smallest sum of a matrix with sorted rows