Solution: The K Weakest Rows in a Matrix (ver. 1)
Tags: algorithms, javascript, java, python
Published: 2021-02-15 09:33:54

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/the-k-weakest-rows-in-a-matrix/discuss/1066579).*

---

*__Note__: This is my first version of a solution post for this problem. I prefer this solution, but my second version technically has a better time complexity (__O(m * log(n + k))__ vs. __O(m * n)__) as well as a better space complexity (__O(k)__ vs. __O(m)__), but it does so by using a __binary search function__, a __max-heap data structure__, and __bit manipulation__, which are fairly complex tools for an "Easy" problem.*

*If you'd like to check out the more complex solution, [you can find the full breakdown over here](https://dev.to/seanpgallivan/solution-the-k-weakest-rows-in-a-matrix-ver-2-1m7c/edit).*

---

####[Leetcode Problem #1337 (*Easy*): The K Weakest Rows in a Matrix](https://leetcode.com/problems/the-k-weakest-rows-in-a-matrix/)

---

***Description:***

*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.*

---

***Examples:***

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]]<br>k = 3
*Output:*|[2,0,3]
*Explanation:*|The number of soldiers for each row is:<br><br>row 0 -> 2<br>row 1 -> 4<br>row 2 -> 1<br>row 3 -> 2<br>row 4 -> 5<br><br>Rows ordered from the weakest to the 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]]<br>k = 2
*Output:*|[0,2]
*Explanation:*|The number of soldiers for each row is:<br><br>row 0 -> 1<br>row 1 -> 4<br>row 2 -> 1<br>row 3 -> 1<br><br>Rows ordered from the weakest to the strongest are [0,2,3,1]

---

***Constraints:***
 - `m == mat.length`
 - `n == mat[i].length`
 - `2 <= n, m <= 100`
 - `1 <= k <= m`
 - `mat[i][j]` is either `0` or `1`.

---

***Idea:***

Since the soldiers are always at the front of each row, we can observe that the first row to show a citizen in any given column is the first index that should be represented in our answer array (**ans**).

That means that we can find the proper elements of **ans** in order by simply iterating through the columns, top to bottom, and pushing the rows to **ans** one at a time as their citizens are exposed. We then just need to keep track of which rows have been finished already with a flag in our visited array (**vis**).

Once we've filled **ans** with the weakest **K** row indexes, we should **return ans**.

---

***Implementation:***

For Javascript, we should use the lightweight typed **Uint8Array** for **vis**.

For Java and C++, we should declare our ans array with a fixed dimension, and then use a separate index variable (**kix**) to place the elements in the proper positions.

---

***Javascript Code:***
```javascript
var kWeakestRows = function(M, K) {
    let y = M.length, x = M[0].length,
        vis = new Uint8Array(y), ans = []
    for (let j = 0; j <= x; j++)
        for (let i = 0; i < y; i++) {
            if (!vis[i] && !M[i][j]) ans.push(i), vis[i]++
            if (ans.length === K) return ans
        }
};
```

---

***Python Code:***
```python
class Solution:
    def kWeakestRows(self, M: List[List[int]], K: int) -> List[int]:
        y, x = len(M), len(M[0])
        vis, ans = [0] * y, []
        for j in range(x+1):
            for i in range(y):
                if not vis[i] and (j == x or not M[i][j]):
                    ans.append(i)
                    vis[i] = 1
                if len(ans) == K: return ans
```

---

***Java Code:***
```java
class Solution {
    public int[] kWeakestRows(int[][] M, int K) {
        int y = M.length, x = M[0].length, kix = 0;
        int[] vis = new int[y], ans = new int[K];
        for (int j = 0; j <= x; j++)
            for (int i = 0; i < y; i++) {
                if (vis[i] == 0 && (j == x || M[i][j] == 0)) {
                    ans[kix++] = i;
                    vis[i]++;
                }
                if (kix == K) return ans;
            }
        return ans;
    }
}
```

---

***C++ Code:***
```c++
class Solution {
public:
    vector<int> kWeakestRows(vector<vector<int>>& M, int K) {
        int y = M.size(), x = M[0].size(), kix = 0;
        vector<int> vis(y), ans(K);
        for (int j = 0; j <= x; j++)
            for (int i = 0; i < y; i++) {
                if (!vis[i] && (j == x || !M[i][j])) {
                    ans[kix++] = i;
                    vis[i]++;
                }
                if (kix == K) return ans;
            }
        return ans;
    }
};
```