Problem: 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.
Example:
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]
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]
Approach: One straight forward approach which comes to mind is sorting. Basically we can sort rows based on strength and then return the weakest k rows. We can also optimize this approach by applying binary search while calculating the strength instead of linear search but these approaches will be expensive as it requires sorting. Let's see how we can solve it without sorting:
Given that all the soldiers comes first (1 comes before 0), if we do vertical traversing (based on columns first instead of rows), we can solve this problem quickly. Basically whenever we see a cell is 0 and it's left cell is 1 then we can add this row to the result as it is the weakest row in the remaining rows because it's strength is lesser than every other remaining row (we are doing vertical traversing).
Implementation in C#:
public int[] KWeakestRows(int[][] mat, int k)
{
int[] weakestRows = new int[k];
int row = mat.Length;
int col = mat[0].Length;
int writeIndex = 0;
for (int j = 0; j < col && writeIndex < k; ++j)
{
for (int i = 0; i < row && writeIndex < k; ++i)
{
if (mat[i][j] == 0 && (j == 0 || mat[i][j - 1] == 1))
{
weakestRows[writeIndex++] = i;
}
}
}
// This is a case when multiple rows has all 1s and we did not find k weakest rows yet
for (int i = 0; i < row && writeIndex < k; ++i)
{
if (mat[i][col -1] == 1)
{
weakestRows[writeIndex++] = i;
}
}
return weakestRows;
}
Complexity: O(m * n) where m is number of rows and n is number of columns
No comments:
Post a Comment