Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in C++

Solution: The K Weakest Rows in a Matrix

Explore how to solve the problem of finding the k weakest rows in a binary matrix by using a modified binary search and a max-heap. This lesson helps you understand how to count soldiers in each row and manage a heap to extract the weakest rows efficiently, enhancing your coding interview skills in algorithms and data structures.

We'll cover the following...

Statement

You are given an m×nm \times n binary matrix of 11’s (representing soldiers) and 00’s (representing civilians). The soldiers are positioned in front of the civilians, i.e., all the 11’s will appear to the left of all the 00’s in each row.

A row ii is weaker than a row jj if any of the following is TRUE:

  • The number of soldiers in row ii is less than the number of soldiers in row jj.

  • Both rows have the same number of soldiers and  ...