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 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
matrix[i][j] is either 0 or 1.
Solution:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace LeetCode.AskGif.Easy.Array
{
public class KWeakestRowsSoln
{
public int[] KWeakestRows(int[][] mat, int k)
{
var map = new Dictionary<int, int>();
for (int i = 0; i < mat.Length; i++)
{
for (int j = 0; j < mat[i].Length; j++)
{
if(mat[i][j] == 1)
{
if (map.ContainsKey(i))
{
map[i]++;
}
else
{
map.Add(i, 1);
}
}
else
{
if (!map.ContainsKey(i))
{
map.Add(i, 0);
}
}
}
}
var sortedCollection = map
.OrderBy(x => x.Value)
.ThenBy(x => x.Key);
var res = new int[k];
int y = 0;
foreach (var item in sortedCollection)
{
res[y] = item.Key;
y++;
if (y==k)
{
break;
}
}
return res;
}
}
}
Time Complexity: O(n^2)
Space Complexity: O(n)
using LeetCode.AskGif.Easy.Array;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using System;
using System.Collections.Generic;
using System.Text;
namespace CodingUnitTest.Easy.Array
{
[TestClass]
public class KWeakestRowsSolnTests
{
[TestMethod]
public void KWeakestRowsSoln_First()
{
var mat = new int[,] {
{ 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 }
};
var k = 3;
var output = new int[]{2, 0, 3};
var res = new KWeakestRowsSoln().KWeakestRows(ArrayMapper(mat), k);
AreEqual(res, output);
}
[TestMethod]
public void KWeakestRowsSoln_Second()
{
var mat = new int[,] {
{ 1, 0, 0, 0 },
{ 1, 1, 1, 1 },
{ 1, 0, 0, 0 },
{ 1, 0, 0, 0 }
};
var k = 2;
var output = new int[] { 0, 2 };
var res = new KWeakestRowsSoln().KWeakestRows(ArrayMapper(mat), k);
AreEqual(res, output);
}
[TestMethod]
public void KWeakestRowsSoln_Third()
{
var mat = new int[,] {
{ 1, 0 },
{ 0, 0 },
{ 1, 0 }
};
var k = 2;
var output = new int[] { 1, 0 };
var res = new KWeakestRowsSoln().KWeakestRows(ArrayMapper(mat), k);
AreEqual(res, output);
}
[TestMethod]
public void KWeakestRowsSoln_Fourth()
{
var mat = new int[,] {
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0 },
{ 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
};
var k = 17;
var output = new int[] { 10, 12, 15, 4, 14, 16, 2, 7, 11, 3, 5, 0, 13, 1, 9, 17, 6 };
var res = new KWeakestRowsSoln().KWeakestRows(ArrayMapper(mat), k);
AreEqual(res, output);
}
private int[][] ArrayMapper(int[,] matrix)
{
var arr = new int[matrix.GetLength(0)][];
for (int i = 0; i < matrix.GetLength(0); i++)
{
arr[i] = new int[matrix.GetLength(1)];
for (int j = 0; j < matrix.GetLength(1); j++)
{
arr[i][j] = matrix[i, j];
}
}
return arr;
}
private void AreEqual(int[] res, int[] output)
{
Assert.AreEqual(res.Length, output.Length);
for (int i = 0; i < res.Length; i++)
{
Assert.AreEqual(res[i], output[i]);
}
}
}
}
Unit Tests:
