# Leetcode 1337: K Weakest Rows In A Matrix

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

*, if the number of soldiers in row*

**j***is less than the number of soldiers in row*

**i***, or they have the same number of soldiers but*

**j***is less than*

**i***. Soldiers are*

**j****always**stand in the frontier of a row, that is, always

*ones*may appear first and then

*zeros*.

Input 1Input: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 = 3Output:[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 2Input:mat = [[1,0,0,0], [1,1,1,1], [1,0,0,0], [1,0,0,0]], k = 2Output:[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

- 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.
- Then sort the output array on the basis of count.
- 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