Leetcode 1337: The K Weakest Rows in a Matrix

Input: The input consists of a binary matrix mat of size m x n, followed by an integer k representing the number of weakest rows to return.

Example: mat = [[1, 1, 0, 0], [1, 1, 1, 0], [1, 0, 0, 0], [1, 1, 1, 1]], k = 2

Constraints:

• 2 <= n, m <= 100

• 1 <= k <= m

• matrix[i][j] is either 0 or 1.

Output: The output should be a list of integers representing the indices of the k weakest rows, ordered from weakest to strongest.

Example: For mat = [[1, 1, 0, 0], [1, 1, 1, 0], [1, 0, 0, 0], [1, 1, 1, 1]], k = 2, the output will be [2, 0].

Constraints:

• The number of rows to return is always valid (1 <= k <= m).

Goal: The goal is to identify the k weakest rows in the matrix and return them in the required order.

Steps:

• 1. Count the number of soldiers (1's) in each row.

• 2. Pair each row's soldier count with its index.

• 3. Sort these pairs first by soldier count, and if two rows have the same count, by their index.

• 4. Extract the indices of the k weakest rows and return them.

Goal: The constraints ensure that the matrix size is manageable for the solution approach, and that k is always within a valid range.

Steps:

• 2 <= n, m <= 100

• 1 <= k <= m

• matrix[i][j] is either 0 or 1.

Assumptions:

• The matrix rows contain only 0's and 1's, with 1's representing soldiers and 0's representing civilians.

• The number of soldiers in a row is always less than or equal to the number of columns.

• Input: Example 1: mat = [[1, 1, 0, 0], [1, 1, 1, 0], [1, 0, 0, 0], [1, 1, 1, 1]], k = 2

• Explanation: The weakest rows are rows 2 (1 soldier) and 0 (2 soldiers).

• Input: Example 2: mat = [[1, 0], [1, 1], [1, 0], [1, 0]], k = 3

• Explanation: The weakest rows are rows 0, 2, and 3 (each with 1 soldier), ordered by their indices.

Approach: To solve this problem, we need to count the number of soldiers in each row and then sort the rows based on the count of soldiers. We can then return the indices of the k weakest rows.

Observations:

• The matrix is binary, making it easy to count soldiers in each row.

• Sorting the rows based on the number of soldiers is a simple way to determine the weakest rows.

• Sorting is an efficient approach given that the matrix size is relatively small (maximum 100x100).

Steps:

• 1. Create an array to store the soldier count for each row.

• 2. Pair each soldier count with the corresponding row index.

• 3. Sort the array of pairs by soldier count and then by row index.

• 4. Extract the indices of the k weakest rows and return them.

Empty Inputs:

• Empty matrices are not expected given the constraints.

Large Inputs:

• Handle matrices up to the size 100x100 efficiently.

Special Values:

• Rows with the same number of soldiers should be sorted by their index.

Constraints:

• Ensure that the sorted rows are correctly ordered first by soldier count, then by row index in case of ties.

vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
    int n=mat[0].size();
    for(int i=0; i<mat.size(); i++){
        mat[i].push_back(i);
    }
    sort(mat.begin(), mat.end());
    vector<int> ans(k);
    for(int i=0; i<k; i++){
        ans[i]=mat[i][n];            
    }
    return ans;
}

1 : Function Definition

vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {

This is the function definition, where the function takes a matrix 'mat' and an integer 'k', and returns the indices of the k weakest rows.

2 : Matrix Column Size

    int n=mat[0].size();

Here we get the number of columns 'n' in the matrix by accessing the size of the first row.

3 : Row Loop Start

    for(int i=0; i<mat.size(); i++){

We loop through each row of the matrix to append the row index to it.

4 : Append Row Index

        mat[i].push_back(i);

For each row, we append its index to the end, which helps in sorting rows by their strengths while keeping track of their original positions.

5 : Sort Matrix

    sort(mat.begin(), mat.end());

We sort the matrix rows in ascending order based on the number of 1s in each row (since the row index is appended, it will keep track of the original positions).

6 : Answer Vector Initialization

    vector<int> ans(k);

We initialize a vector 'ans' of size 'k' to store the indices of the k weakest rows.

7 : Answer Population Loop Start

    for(int i=0; i<k; i++){

We loop through the first k rows in the sorted matrix to extract their original indices.

8 : Populate Answer Vector

        ans[i]=mat[i][n];

For each of the k weakest rows, we store the original index of the row (which is stored at the last position in the row after appending).

9 : Return Answer

    return ans;

Finally, we return the vector 'ans', which contains the indices of the k weakest rows.

Best Case: O(m log m), where m is the number of rows in the matrix.

Average Case: O(m log m)

Worst Case: O(m log m)

Description: Sorting the rows takes O(m log m), where m is the number of rows.

Best Case: O(m)

Worst Case: O(m)

Description: The space complexity is O(m) due to the storage of the soldier counts and row indices.

Leetcode 1337: The K Weakest Rows in a Matrix

Explore →