DEV Community

Cover image for Solution: The K Weakest Rows in a Matrix (ver. 1)
seanpgallivan
seanpgallivan

Posted on

Solution: The K Weakest Rows in a Matrix (ver. 1)

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.


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.


Leetcode Problem #1337 (Easy): 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]]
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]
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 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]

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:

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
        }
};
Enter fullscreen mode Exit fullscreen mode

Python Code:

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
Enter fullscreen mode Exit fullscreen mode

Java Code:

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;
    }
}
Enter fullscreen mode Exit fullscreen mode

C++ Code:

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;
    }
};
Enter fullscreen mode Exit fullscreen mode

Top comments (0)