Solution Approach

The implementation follows these steps:

1. Extract matrix dimensions: First, we get m (number of rows) and n (number of columns) from the input matrix.

2. Count soldiers in each row using the canonical binary search template: For each row, we find the first 0 (which gives us the soldier count):

   left, right = 0, num_cols - 1
   first_zero_index = -1
   
   while left <= right:
       mid = (left + right) // 2
       if row[mid] == 0:
           first_zero_index = mid
           right = mid - 1
       else:
           left = mid + 1
   
   return num_cols if first_zero_index == -1 else first_zero_index

   The feasible condition is row[mid] == 0 (found a civilian). When we find a 0, we record its position and search left for an earlier 0. When we find a 1, we search right. If no 0 is found (first_zero_index == -1), all elements are soldiers, so we return num_cols.

3. Create and sort row indices:

   • Generate a list of indices [0, 1, 2, ..., m-1]
   • Sort these indices based on their corresponding soldier counts
   • Since Python's sort is stable, rows with equal soldier counts maintain their original order (smaller indices first)

4. Return k weakest rows: Simply slice the sorted indices list to get the first k elements.

The time complexity is O(m * log n + m * log m) where:

• O(m * log n) for binary search on each of the m rows
• O(m * log m) for sorting the indices

The space complexity is O(m) for storing the soldier counts and indices lists.

Example Walkthrough

Let's walk through a concrete example with a small matrix and k = 3:

mat = [[1,1,0,0,0],    # row 0: 2 soldiers
       [1,1,1,1,0],    # row 1: 4 soldiers
       [1,0,0,0,0],    # row 2: 1 soldier
       [1,1,1,0,0]]    # row 3: 3 soldiers
k = 3

Step 1: Extract dimensions

• m = 4 (4 rows)
• n = 5 (5 columns)

Step 2: Count soldiers in each row using binary search

For row 0: [1,1,0,0,0]

• Reverse it: [0,0,0,1,1]
• bisect_right([0,0,0,1,1], 0) returns 3 (position after last 0)
• Soldiers = 5 - 3 = 2

For row 1: [1,1,1,1,0]

• Reverse it: [0,1,1,1,1]
• bisect_right([0,1,1,1,1], 0) returns 1
• Soldiers = 5 - 1 = 4

For row 2: [1,0,0,0,0]

• Reverse it: [0,0,0,0,1]
• bisect_right([0,0,0,0,1], 0) returns 4
• Soldiers = 5 - 4 = 1

For row 3: [1,1,1,0,0]

• Reverse it: [0,0,1,1,1]
• bisect_right([0,0,1,1,1], 0) returns 2
• Soldiers = 5 - 2 = 3

So ans = [2, 4, 1, 3] (soldier counts for rows 0, 1, 2, 3)

Step 3: Sort row indices by soldier count

• Start with idx = [0, 1, 2, 3]
• Sort by soldier count:
  • Row 2 has 1 soldier (weakest)
  • Row 0 has 2 soldiers
  • Row 3 has 3 soldiers
  • Row 1 has 4 soldiers (strongest)
• After sorting: idx = [2, 0, 3, 1]

Step 4: Return k weakest rows

• Take first 3 elements: [2, 0, 3]

The answer is [2, 0, 3], representing the 3 weakest rows in order from weakest to strongest.

Time and Space Complexity

Time Complexity: O(m * n + m * log(m))

• Creating the ans list requires iterating through each row and for each row:
  • Reversing the row takes O(n) time
  • bisect_right on the reversed row takes O(log n) time
  • Overall for all m rows: O(m * n) (since n > log n)
• Creating the idx list takes O(m) time
• Sorting the idx list based on the values in ans takes O(m * log m) time
• Slicing to get the first k elements takes O(k) time

Total: O(m * n + m * log m) where m is the number of rows and n is the number of columns

Space Complexity: O(m)

• The ans list stores m integers: O(m) space
• The idx list stores m indices: O(m) space
• The reversed row row[::-1] creates a temporary copy: O(n) space (but this is reused for each row, not cumulative)
• The sorting operation may use O(log m) space for the recursion stack (in case of quicksort/mergesort)
• The output slice idx[:k] takes O(k) space

Total auxiliary space (excluding output): O(m + n), which simplifies to O(m) when m ≥ n or O(n) when n > m

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Using Wrong Binary Search Template Variant

A common mistake is using a different binary search variant that doesn't match the canonical template:

Incorrect approach:

# Using bisect functions instead of explicit binary search
soldier_counts = [bisect.bisect_right(row[::-1], 0) for row in mat]

# Using while left < right with right = mid
left, right = 0, n
while left < right:
    mid = (left + right) // 2
    if row[mid] == 0:
        right = mid  # Wrong! Should be right = mid - 1
    else:
        left = mid + 1
return left  # Wrong! Should track first_zero_index

Why it's problematic: Different variants have different behaviors and are harder to reason about consistently. The canonical template with first_zero_index = -1, while left <= right, and right = mid - 1 provides a consistent pattern.

Correct approach:

left, right = 0, num_cols - 1
first_zero_index = -1

while left <= right:
    mid = (left + right) // 2
    if row[mid] == 0:
        first_zero_index = mid
        right = mid - 1
    else:
        left = mid + 1

return num_cols if first_zero_index == -1 else first_zero_index

2. Inefficient Linear Search Instead of Binary Search

A common mistake is using a simple loop to count soldiers, which defeats the purpose of having a sorted row structure:

Incorrect approach:

# Inefficient O(n) search per row
soldier_counts = [sum(row) for row in mat]  # Works but inefficient
# or
soldier_counts = [row.count(1) for row in mat]  # Also O(n) per row

Why it's problematic: Since each row is already sorted (all 1s before 0s), we can use binary search for O(log n) complexity per row instead of O(n).

3. Incorrect Handling of Tie-Breaking

When multiple rows have the same soldier count, the row with the smaller index should be considered weaker. A pitfall is not preserving this ordering:

Incorrect approach:

# Losing the original indices entirely:
soldier_counts.sort()  # This loses row index information!

Correct approach:

# Python's sort is stable, so this naturally preserves index order for ties
row_indices.sort(key=lambda i: soldier_counts[i])
# Or explicitly include index in sort key:
row_indices.sort(key=lambda i: (soldier_counts[i], i))

4. Edge Case: All Soldiers or All Civilians

Failing to handle rows that contain only 1s or only 0s:

# If a row is all 1s: [1,1,1,1]
# Binary search never finds a 0, so first_zero_index stays -1
# We must return num_cols (all are soldiers)

# If a row is all 0s: [0,0,0,0]
# Binary search finds 0 at index 0
# We return first_zero_index = 0 (no soldiers)

The template handles these correctly by checking first_zero_index == -1 after the loop.