We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

The K Weakest Rows in a Matrix

Number: 1463

Difficulty: Easy

Paid? No

Companies: Google, Amazon

Problem Description

Given an m x n binary matrix where each row represents soldiers (1's) followed by civilians (0's), determine the indices of the k weakest rows ordered from weakest to strongest. A row is weaker if it has fewer soldiers, and if equal, the row with the lower index is considered weaker.

Key Insights

  • Each row's soldier count can be obtained either by summing the row or using binary search since all 1's are followed by 0's.
  • Rows are compared based on the count of soldiers and, in case of ties, by their original indices.
  • Sorting or a heap can be used to efficiently determine the k weakest rows.

Space and Time Complexity

Time Complexity: O(m log n + m log m) where O(m log n) is for counting soldiers via binary search in each row and O(m log m) is for sorting the rows. Space Complexity: O(m) for storing soldier counts and row indices.

Solution

The idea is to iterate over each row and count the number of 1's using an efficient method such as binary search since the row is sorted with all 1's on the left. We then pair each count with its row index and sort these pairs. Finally, we select the first k indices from the sorted list as our result. This approach leverages sorting to satisfy the comparison criteria including the tie-breaker on row indices.

Code Solutions

# Python solution for k weakest rows in a matrix

def kWeakestRows(mat, k):
    # Helper function: binary search to count soldiers in the row
    def countSoldiers(row):
        left, right = 0, len(row)
        # Find the first occurrence of '0' using binary search
        while left < right:
            mid = (left + right) // 2
            if row[mid] == 1:
                left = mid + 1
            else:
                right = mid
        return left  # left equals number of 1's
    
    # Pair each row's soldier count with its index
    row_strength = []
    for index, row in enumerate(mat):
        soldiers = countSoldiers(row)
        row_strength.append((soldiers, index))
    
    # Sort by soldier count first, then row index as tie-breaker
    row_strength.sort(key=lambda x: (x[0], x[1]))
    
    # Extract the indices of the first k rows from the sorted list
    return [index for _, index in row_strength[:k]]

# Example usage:
# 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
# print(kWeakestRows(mat, k))  # Output: [2, 0, 3]
← Back to All Questions