Skip to main content
Talentd

The K Weakest Rows in a Matrix - Solution & Explanation

EasyArrayBinary SearchSortingHeap (Priority Queue)16 min readAsked at: Amazon, Microsoft, Meta +2
Practice this problem

Problem Statement

You are given an m x n binary matrix mat of 1's (representing soldiers) and 0's (representing civilians). The soldiers are positioned in front of the civilians. That is, all the 1's will appear to the left of all the 0's in each row.

A row i is weaker than a row j if one of the following is true:

  • The number of soldiers in row i is less than the number of soldiers in row j.
  • Both rows have the same number of soldiers and i < j.

Return the indices of the k weakest rows in the matrix ordered from weakest to strongest.

 

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]
Explanation: 
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]
Explanation: 
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.

Approach Overview

Problem Overview: You are given a matrix where each row represents soldiers (1s) followed by civilians (0s). A row is weaker if it has fewer soldiers, or if the counts are equal but the row index is smaller. Return the indices of the k weakest rows in ascending order of strength.

Approach 1: Simple Counting and Sorting (Time: O(mn + m log m), Space: O(m))

Iterate through each row and count the number of soldiers by scanning the entire row. Store pairs like (soldierCount, rowIndex) in an array. After processing all rows, sort the array first by soldier count and then by row index. Finally, return the first k indices from the sorted result. This approach relies on straightforward iteration over the array and standard sorting. It is simple to implement and works well when matrix dimensions are small.

Approach 2: Binary Search for Counting (Time: O(m log n + m log m), Space: O(m))

Each row is sorted with all soldiers appearing before civilians. Instead of scanning the entire row, use binary search to find the first 0. The index of that position equals the number of soldiers in the row. Repeat this for every row and store (soldierCount, rowIndex). Sort the pairs and return the first k indices. This reduces the counting step from O(n) per row to O(log n), which is useful when rows are large.

Alternative Optimization: Min Heap / Priority Queue (Time: O(m log n + m log k), Space: O(k))

Instead of sorting all rows, maintain a heap that tracks the k weakest rows seen so far. For each row, compute the soldier count (via binary search or scan) and push the pair into a heap (priority queue). If the heap grows larger than k, remove the strongest element. This avoids sorting the entire list and is more efficient when m is large but k is small.

Recommended for interviews: The binary search counting approach is usually the expected solution because it leverages the sorted row property and improves counting efficiency. Implementing the simple counting version first demonstrates clarity, while adding binary search or a heap shows deeper algorithmic optimization.

Approach 1: Approach 1: Simple Counting and Sorting

In this approach, we directly count the number of soldiers in each row by iterating through the elements of the row, and then sort the rows based on the count followed by their index to determine the order.

Steps to implement:

  • Iterate over each row and count the number of soldiers until a 0 is encountered.
  • Store the count along with the row index in a list of tuples (or pair structures).
  • Sort the list based on the number of soldiers first, and row index as a tiebreaker.
  • Extract the top 'k' indices from the sorted list.

The C solution involves using a two-dimensional array to track the number of soldiers and their respective row indices. We then use the quicksort function with a custom comparator to sort this array by soldiers' count first and indices as a tiebreaker. Finally, extract the indices of the weakest rows.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m*n + m*log m) due to counting and sorting the rows.

Space Complexity: O(m) to store the row strength information.

Try this approach in the editor β†’

Approach 2: Approach 2: Binary Search for Counting

This approach uses binary search to efficiently count the number of soldiers in each row. Given that soldiers are always positioned before civilians, binary search can help quickly find the first civilian and thus the count of soldiers.

Implementation steps:

  • Use binary search on each row to determine the position of the first 0.
  • The position found indicates the number of soldiers in that row.
  • Store the count along with the row index similarly to approach 1.
  • Sort and determine the top 'k' weakest rows as before.

This solution optimizes soldier count using binary search in each row. This reduces the time complexity to efficiently find each row's strength before sorting and extracting indices.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m*log n + m*log m) due to binary search for counting and sorting rows.

Space Complexity: O(m), for maintaining strength array storage.

Try this approach in the editor β†’

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor β†’

Complexity Comparison

ApproachComplexity
Approach 1: Simple Counting and Sorting

Time Complexity: O(m*n + m*log m) due to counting and sorting the rows.

Space Complexity: O(m) to store the row strength information.

Approach 2: Binary Search for Counting

Time Complexity: O(m*log n + m*log m) due to binary search for counting and sorting rows.

Space Complexity: O(m), for maintaining strength array storage.

Default Approachβ€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Counting + SortingO(mn + m log m)O(m)Best for simple implementation when matrix size is small
Binary Search + SortingO(m log n + m log m)O(m)When rows are sorted and you want faster soldier counting
Binary Search + HeapO(m log n + m log k)O(k)Useful when number of rows is large but only k weakest are needed

Video Solution

The K Weakest Rows in a Matrix | Live Coding with Explanation | Leetcode - 1337 β€’ Algorithms Made Easy β€’ 10,471 views views

Watch 9 more video solutions β†’

Frequently Asked Questions

Is The K Weakest Rows in a Matrix easy or hard?
The K Weakest Rows in a Matrix is classified as an Easy problem on LeetCode with a high acceptance rate. The core idea involves counting soldiers in each row and sorting, while binary search provides a small optimization for larger inputs.
The K Weakest Rows in a Matrix Python/Java solution
Python and Java solutions typically compute soldier counts using either a loop or binary search, store pairs of (count, index), and then sort them. Python often uses tuples and the built-in sort, while Java commonly uses arrays with a custom comparator or a priority queue.
How to solve The K Weakest Rows in a Matrix in O(m log n)?
Use binary search on every row to locate the first 0, which directly gives the soldier count. This takes O(log n) per row, so counting across m rows costs O(m log n). Then use a heap of size k or sorting to determine the k weakest rows.
What is the best approach for The K Weakest Rows in a Matrix?
Binary search combined with sorting or a heap is the most efficient approach. Because each row contains soldiers (1s) followed by civilians (0s), binary search can find the soldier count in O(log n) time. After computing counts for all rows, sort them or maintain a heap to extract the k weakest rows.
Is The K Weakest Rows in a Matrix asked at Google/Amazon/Meta?
This problem appears frequently in coding interview practice sets and is commonly associated with companies like Amazon and Google. It tests basic matrix processing, sorting, and binary search optimization, which are common interview topics.
What data structure is used in The K Weakest Rows in a Matrix?
Typical solutions use arrays to store (soldierCount, rowIndex) pairs and apply sorting. Optimized implementations may use binary search for counting and a heap or priority queue to track the k weakest rows efficiently.
What is the time complexity of The K Weakest Rows in a Matrix?
The straightforward solution scans each row and sorts the results, giving O(mn + m log m) time. Using binary search reduces counting to O(m log n), and sorting adds O(m log m). A heap optimization can reduce sorting overhead to O(m log k).

Ready to solve this problem?

Practice The K Weakest Rows in a Matrix with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays