LeetCode 1337 - The K Weakest Rows in a Matrix

Here is a comprehensive, detailed solution guide for LeetCode 1337 following your exact instructions. The problem provid

leetcodeeasyarraybinary-searchsortingheap-(priority-queue)matrix

LeetCode Problem 1337

Difficulty: 🟢 Easy
Topics: Array, Binary Search, Sorting, Heap (Priority Queue), Matrix

Solution

Here is a comprehensive, detailed solution guide for LeetCode 1337 following your exact instructions.

Problem Understanding

The problem provides a binary m x n matrix mat, where each element is either 1 (representing a soldier) or 0 (representing a civilian). In each row, soldiers are always positioned before civilians, meaning all 1s appear on the left side of a row, followed by 0s. The task is to identify the k weakest rows, where a row's weakness is determined primarily by the number of soldiers it contains. If two rows have the same number of soldiers, the row with the smaller index is considered weaker.

The input consists of a matrix and an integer k. The output is a list of row indices of the k weakest rows, ordered from weakest to strongest.

Constraints tell us that the matrix dimensions are moderate (2 <= m, n <= 100), so a straightforward solution that checks every row is feasible but not necessarily optimal. Edge cases include rows that are entirely soldiers, entirely civilians, or rows that tie in soldier count.

Approaches

The brute-force approach involves counting the number of soldiers in each row by iterating through all elements, storing these counts along with their row indices, then sorting the list by soldier count and row index. This approach works but does not leverage the fact that all 1s are on the left, so counting can be optimized.

The optimal approach uses binary search within each row to find the number of soldiers. Because all soldiers are to the left, the first occurrence of 0 indicates the boundary. Once we know the soldier counts, we pair each count with its row index, then sort based on count and index to retrieve the weakest rows efficiently.

Approach Time Complexity Space Complexity Notes
Brute Force O(m * n + m log m) O(m) Count soldiers linearly, then sort rows by count
Optimal O(m * log n + m log m) O(m) Use binary search to count soldiers, then sort by count

Algorithm Walkthrough

  1. Initialize an empty list to store pairs of (soldier_count, row_index) for all rows.

  2. For each row in the matrix:

  3. Perform binary search to find the first 0. The index of this 0 is the number of soldiers in the row.

  4. Store the pair (soldier_count, row_index) in the list.

  5. Sort the list of pairs first by soldier count and then by row index.

  6. Extract the first k row indices from the sorted list.

  7. Return these indices as the result.

Why it works: Binary search ensures we efficiently find the number of soldiers in O(log n) time per row, and sorting the pairs guarantees that ties are resolved by the row index. Therefore, the output always represents the k weakest rows correctly.

Python Solution

from typing import List
import bisect

class Solution:
    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
        soldier_counts = []
        
        for index, row in enumerate(mat):
            # Use binary search to find the first 0 in the row
            count = bisect.bisect_left(row, 0)
            soldier_counts.append((count, index))
        
        # Sort by soldier count, then by row index
        soldier_counts.sort()
        
        # Extract the first k indices
        return [index for _, index in soldier_counts]

The implementation first uses bisect_left from Python's bisect module to locate the first 0 in each row, effectively counting the soldiers in O(log n). We pair this count with the row index, sort the list, and then extract the k weakest row indices. This matches the algorithm steps precisely.

Go Solution

import "sort"

func kWeakestRows(mat [][]int, k int) []int {
    type pair struct {
        count int
        index int
    }
    
    soldierCounts := make([]pair, len(mat))
    
    for i, row := range mat {
        left, right := 0, len(row)
        for left < right {
            mid := left + (right-left)/2
            if row[mid] == 1 {
                left = mid + 1
            } else {
                right = mid
            }
        }
        soldierCounts[i] = pair{count: left, index: i}
    }
    
    sort.Slice(soldierCounts, func(i, j int) bool {
        if soldierCounts[i].count == soldierCounts[j].count {
            return soldierCounts[i].index < soldierCounts[j].index
        }
        return soldierCounts[i].count < soldierCounts[j].count
    })
    
    result := make([]int, k)
    for i := 0; i < k; i++ {
        result[i] = soldierCounts[i].index
    }
    
    return result
}

In Go, we define a pair struct to store (count, index) and use a binary search loop to count soldiers. The slice is sorted using sort.Slice with a custom comparator that respects the soldier count and row index. We then collect the first k indices into the result slice.

Worked 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

Step 1: Count soldiers using binary search

Row 0: 2 soldiers
Row 1: 4 soldiers
Row 2: 1 soldier
Row 3: 2 soldiers
Row 4: 5 soldiers

Step 2: Pair with indices

[(2,0), (4,1), (1,2), (2,3), (5,4)]

Step 3: Sort by count, then index

[(1,2), (2,0), (2,3), (4,1), (5,4)]

Step 4: Take first k indices

[2,0,3]

Example 2:

Input:

mat = [[1,0,0,0],
       [1,1,1,1],
       [1,0,0,0],
       [1,0,0,0]], k = 2

Soldier counts: [1,4,1,1]

Pairs: [(1,0),(4,1),(1,2),(1,3)]

Sorted: [(1,0),(1,2),(1,3),(4,1)]

Result: [0,2]

Complexity Analysis

Measure Complexity Explanation
Time O(m * log n + m log m) Binary search for each row takes O(log n), sorting m elements takes O(m log m)
Space O(m) We store (count, index) for each row

The complexity is efficient for the given constraints of m,n <= 100, so the solution executes comfortably within limits.

Test Cases

# provided examples
assert Solution().kWeakestRows([[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]], 3) == [2,0,3]  # example 1
assert Solution().kWeakestRows([[1,0,0,0],[1,1,1,1],[1,0,0,0],[1,0,0,0]], 2) == [0,2]  # example 2

# all soldiers
assert Solution().kWeakestRows([[1,1],[1,1]], 2) == [0,1]  # rows tie, indices ascending

# all civilians
assert Solution().kWeakestRows([[0,0],[0,0]], 1) == [0]  # tie with zero soldiers

# mixed rows with tie-breaking
assert Solution().kWeakestRows([[1,1,0],[1,0,0],[1,1,0],[0,0,0]], 4) == [3,1,0,2]  # mixed strengths

# minimum input
assert Solution().kWeakestRows([[1,0]], 1) == [0]  # single row
Test Why
example 1 verifies counting and ordering correctness
example 2 verifies tie-breaking and k selection
all soldiers tests tie-breaking by index
all civilians tests rows with zero soldiers
mixed rows tests multiple ties and ordering
minimum input tests smallest allowed matrix

Edge Cases

One edge case occurs when all rows have the same number of soldiers. A naive solution might forget to sort by row index, but our solution sorts by (count, index) ensuring correct order.

Another edge case is a row full of soldiers or full of civilians. Binary search handles both correctly: if all 1s, bisect_left returns n; if all 0s, it returns