algoadvance

Leetcode 1337. The K Weakest Rows in a Matrix

Problem Statement:

Given a m x n binary matrix mat of 1’s (representing soldiers) and 0’s (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 standing in front of civilians, that is, all the 1’s will appear to the left of all the 0’s in each row.

Clarifying Questions:

  1. Input Validity:
    • What if k is greater than the number of rows?
    • Should we assume all rows have at least one 0’s to ensure a mixture of soldiers and civilians?
  2. Output Requirements:
    • Should the output be a list of integers indicating the indices of the rows?

Strategy:

  1. Count Soldiers in Each Row:
    • Iterate through each row to count the number of 1s. Since soldiers (1s) always appear before civilians (0s), we can use binary search to find the first 0 for efficiency.
  2. Store and Sort:
    • Store the count along with the row index.
    • Sort these pairs first by the count of soldiers and then by the row index.
  3. Select Top K:
    • Extract the indices of the top k weakest rows from the sorted list.

Code:

Here is the implementation of the strategy in Java:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Solution {
    public int[] kWeakestRows(int[][] mat, int k) {
        List<int[]> soldiersCount = new ArrayList<>();
        
        // Step 1: Count the number of soldiers in each row and pair with the row index
        for (int i = 0; i < mat.length; i++) {
            int soldiers = countSoldiers(mat[i]);
            soldiersCount.add(new int[]{soldiers, i});
        }
        
        // Step 2: Sort the list by the number of soldiers, then by row index
        Collections.sort(soldiersCount, (a, b) -> {
            if (a[0] != b[0]) {
                return a[0] - b[0]; // Compare by number of soldiers
            } else {
                return a[1] - b[1]; // Compare by row index
            }
        });
        
        // Step 3: Extract the indices of the k weakest rows
        int[] weakestRows = new int[k];
        for (int i = 0; i < k; i++) {
            weakestRows[i] = soldiersCount.get(i)[1];
        }
        
        return weakestRows;
    }
    
    // Helper method to count soldiers using binary search
    private int countSoldiers(int[] row) {
        int left = 0;
        int right = row.length;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (row[mid] == 1) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return left;
    }
}

Time Complexity:

  1. Counting Soldiers: O(m * log(n)) - counting soldiers in each of the m rows using binary search (log(n)).
  2. Sorting Rows: O(m * log(m)) - sorting the m rows based on soldier count and row indices.

Thus, the overall time complexity is: [ O(m \log n + m \log m) ]

This approach ensures that the matrix is processed efficiently and the weakest rows are identified correctly.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI