Problem link – https://leetcode.com/problems/the-k-weakest-rows-in-a-matrix/

This Leetcode – 1337: The K Weakest Rows in a Matrix problem is present in the binary search, easy category list.

Problem Statement

Given a m * n matrix mat of ones (representing soldiers) and zeros (representing civilians), return the indexes of the k weakest rows in the matrix ordered from the weakest to the strongest.

A row i is weaker than row j, if the number of soldiers in row i is less than the number of soldiers in row j, or they have the same number of soldiers but i is less than j. Soldiers are always stand in the frontier of a row, that is, always ones may appear first and then zeros.

Input 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 for each row is: 
row 0 -> 2 
row 1 -> 4 
row 2 -> 1 
row 3 -> 2 
row 4 -> 5 
Rows ordered from the weakest to the strongest are [2,0,3,1,4]

Input 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 for each row is: 
row 0 -> 1 
row 1 -> 4 
row 2 -> 1 
row 3 -> 1 
Rows ordered from the weakest to the strongest are [0,2,3,1]

Approach

1. We need to find the total number of one(1) present in each row of a matrix and store that count and index in an output array. We will use modified binary to find the count.
2. Then sort the output array on the basis of count.
3. Return the first k counts in the form of an array.

Code

Approach 1: Brute force

Time complexity – O(n^2)

Approach 2: Using Binary Search

Time complexity – O(n logn)

Thank you for Reading