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.
1import java.util.*;
2
3class Solution {
4 public int[] kWeakestRows(int[][] mat, int k) {
5 int m = mat.length;
6 int n = mat[0].length;
7 int[][] strength = new int[m][2];
8 for (int i = 0; i < m; i++) {
9 int soldierCount = 0;
10 for (int j = 0; j < n; j++) {
11 if (mat[i][j] == 1) {
12 soldierCount++;
13 } else {
14 break;
15 }
16 }
17 strength[i][0] = soldierCount;
18 strength[i][1] = i;
19 }
20 Arrays.sort(strength, Comparator.comparingInt(a -> a[0]));
21 int[] result = new int[k];
22 for (int i = 0; i < k; i++) {
23 result[i] = strength[i][1];
24 }
25 return result;
26 }
27}The Java solution follows a similar logic by creating a 2D array to hold soldier count and row indices. Arrays.sort combined with a comparator is used to sort based on soldier counts followed by natural order of indices.
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.
This solution optimizes soldier count using binary search in each row. This reduces the time complexity to efficiently find each row's strength before sorting and extracting indices.