← Back to Index

📚 The K Weakest Rows in a Matrix – Java Cheat Sheet

📌 What Is It?

The The K Weakest Rows in a Matrix problem involves finding the K weakest rows in a binary matrix. A row's weakness is determined by the number of 1s in it, and in case of a tie, the row with the smaller index is weaker.

🧱 Pattern Template

class Solution {
    public int[] kWeakestRows(int[][] mat, int k) {
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
            (a, b) -> a[0] == b[0] ? b[1] - a[1] : b[0] - a[0]
        );

        for (int i = 0; i < mat.length; i++) {
            int soldierCount = countSoldiers(mat[i]);
            maxHeap.offer(new int[]{soldierCount, i});

            if (maxHeap.size() > k) {
                maxHeap.poll();
            }
        }

        int[] result = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            result[i] = maxHeap.poll()[1];
        }

        return result;
    }

    private int countSoldiers(int[] row) {
        int left = 0, 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

• Counting Soldiers: O(R log C) – Binary search for each row.
• Heap Operations: O(R log K) – Maintaining a max-heap of size K.
• Overall Complexity: O(R log C + R log K), where R is the number of rows and C is the number of columns.

✅ Use Cases

• Finding the weakest rows in a binary matrix
• Applications in ranking and prioritization problems

📘 Common LeetCode Problems

• 1337. The K Weakest Rows in a Matrix [Easy] Heap

🧪 Example: The K Weakest Rows in a Matrix

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:
- Row 2 has 1 soldier, row 0 has 2 soldiers, and row 3 has 2 soldiers.
- These are the 3 weakest rows.

▶️ View Animation

💡 Pro Tips

• Use binary search to efficiently count the number of soldiers in each row.
• Maintain a max-heap of size K to track the weakest rows.
• Edge cases: rows with all 0s or all 1s, and ties in soldier counts.