Sponsored
Sponsored
In this approach, we directly count the number of soldiers in each row by iterating through the elements of the row, and then sort the rows based on the count followed by their index to determine the order.
Steps to implement:
Time Complexity: O(m*n + m*log m) due to counting and sorting the rows.
Space Complexity: O(m) to store the row strength information.
1using System;
2using System.Collections.Generic;
3using System.Linq;
4
5public class Solution {
6 public int[] KWeakestRows(int[][] mat, int k) {
7 var rowStrength = new List<Tuple<int, int>>();
8 for (int i = 0; i < mat.Length; i++) {
9 int soldierCount = 0;
10 for (int j = 0; j < mat[i].Length; j++) {
11 if (mat[i][j] == 1) soldierCount++;
12 else break;
13 }
14 rowStrength.Add(new Tuple<int, int>(soldierCount, i));
}
rowStrength.Sort();
return rowStrength.Take(k).Select(x => x.Item2).ToArray();
}
}This C# solution utilizes a List of Tuples to store each row’s soldier count and index. The list is sorted using the Default Tuple comparison and indices of the weakest rows are selected using Linq Take function.
This approach uses binary search to efficiently count the number of soldiers in each row. Given that soldiers are always positioned before civilians, binary search can help quickly find the first civilian and thus the count of soldiers.
Implementation steps:
Time Complexity: O(m*log n + m*log m) due to binary search for counting and sorting rows.
Space Complexity: O(m), for maintaining strength array storage.
#include <algorithm>
using namespace std;
int countSoldiers(const vector<int>& row) {
int low = 0, high = row.size() - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (row[mid] == 1) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return low;
}
vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
vector<pair<int, int>> rowStrength;
for (int i = 0; i < mat.size(); ++i) {
int soldierCount = countSoldiers(mat[i]);
rowStrength.push_back({soldierCount, i});
}
sort(rowStrength.begin(), rowStrength.end());
vector<int> result;
for (int i = 0; i < k; ++i) {
result.push_back(rowStrength[i].second);
}
return result;
}The C++ solution employs a helper function for binary search to count soldiers and then proceeds with the usual sorting and extraction of weakest row indices.