Leetcode Study Day 1

The K Weakest Rows in a Matrix

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.

My solution

Count soliders in the row

Since defining whether a row is weak, is based on the number of 1s in this row. So we can count how many 1s in a row first.

And since the 1s are always infront of the 0s, so once there is a 0 in the row, we can stop the loop. We then push the number of 1s and the index of the row into a vector.

vector<pair<int, int>> strength;
for (int i = 0; i < mat.size(); i++){
    int count = 0;
    for (int j =0; j < mat[i].size(); j++){
    if (mat[i][j] == 1) 
        count ++;
        else
        break;
    }
    strength.push_back({count, i});
}

Sort the vector

After getting a vector of number of soliders and the index of each rows,
we then sort this vector based on this idea: we first consider the number of soliders and put the index of row with less soliders number in front of the row with more soliders number. If the number of soldiers are the same, then we compare the index of the row, and put the row with smaller index in front of the row with bigger index.

Explanation of this sort function: the first and the second parameters are the start and end position of the array, the third parameter is a lambda function, which is used to compare two elements in the array by the logic inside the function.

sort(strength.begin(), strength.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
        if (a.first != b.first) {
            return a.first < b.first;
        } else {
            return a.second < b.second;
        }
    });

Get the result

After sorting the vector, we can get the result by pushing the index of the row into a vector.

vector<int> result;
for (int i = 0; i < k; ++i) {
    result.push_back(strength[i].second);
}
return result;

The full code

class Solution {
public:
    vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
      vector<pair<int, int>> strength;
        for (int i = 0; i < mat.size(); i++){
          int count = 0;
          for (int j =0; j < mat[i].size(); j++){
            if (mat[i][j] == 1) 
              count ++;
             else
              break;
          }
          strength.push_back({count, i});
        }
      // Sort the strength vector based on the number of soldiers and then by row index
      sort(strength.begin(), strength.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
        if (a.first != b.first) {
            return a.first < b.first;
        } else {
            return a.second < b.second;
        }
    });

    // Extract the first k indices from the sorted strength vector
    vector<int> result;
    for (int i = 0; i < k; ++i) {
        result.push_back(strength[i].second);
    }
    return result;
    }
};