The K Weakest Rows in a Matrix - Practice Coding Problems

The K Weakest Rows in a Matrix - Problem

Imagine you're a military strategist analyzing the defensive strength of different battle formations. You have an m x n binary matrix representing a battlefield where 1's represent soldiers and 0's represent civilians.

The key insight is that soldiers always position themselves in front of civilians - meaning all 1's appear to the left of all 0's in each row.

Your mission: Identify the k weakest rows based on these rules:

A row is weaker if it has fewer soldiers
If two rows have the same number of soldiers, the one with the smaller index is weaker

Return the indices of the k weakest rows, ordered from weakest to strongest.

Example: If row 0 has 2 soldiers, row 1 has 1 soldier, and row 2 has 3 soldiers, and k=2, you'd return [1, 0] because row 1 is weakest (1 soldier), followed by row 0 (2 soldiers).

Input & Output

example_1.py — Basic Case

$ 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]

💡 Note: Row 2 has 1 soldier (weakest), row 0 has 2 soldiers, row 3 has 2 soldiers (but comes after row 0), so the 3 weakest are [2,0,3]

example_2.py — Tie Breaking

$ Input: mat = [[1,0,0,0],[1,1,1,1],[1,0,0,0],[1,0,0,0]], k = 2

› Output: [0,2]

💡 Note: Rows 0, 2, 3 all have 1 soldier each. Since we need k=2 weakest and there's a tie, we pick the ones with smaller indices: [0,2]

example_3.py — All Different

$ Input: mat = [[1,1,1],[1,1,0],[1,0,0]], k = 2

› Output: [2,1]

💡 Note: Row 2 has 1 soldier (weakest), row 1 has 2 soldiers (second weakest), row 0 has 3 soldiers (strongest)

Constraints

m == mat.length
n == mat[i].length
2 ≤ n, m ≤ 100
1 ≤ k ≤ m
matrix[i][j] is either 0 or 1
All 1's appear before all 0's in each row (soldiers before civilians)

Visualization

Tap to expand

Understanding the Visualization

Count Soldiers

For each unit (row), count the number of soldiers

Rank by Strength

Determine which units are weakest based on soldier count

Handle Ties

When units have same strength, prioritize by unit number (index)

Select Top K

Choose the k weakest units for reinforcement

Key Takeaway

🎯 Key Insight: Since soldiers always position before civilians in each row, we can use binary search to find the soldier count in O(log n) time instead of scanning the entire row.

Asked in

G Google 15 a Amazon 12 f Meta 8 ⊞ Microsoft 6

The optimal approach uses binary search to efficiently count soldiers in O(log n) per row, leveraging the fact that soldiers always appear before civilians. Combined with sorting, this gives us O(m log n + m log m) time complexity, which is better than the brute force O(m*n + m log m) for wide matrices.

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search Optimization	O(m log n + m log m)	O(m)	Use binary search to count soldiers efficiently, then sort by strength
Brute Force (Count and Sort)	O(m*n + m log m)	O(m)	Count soldiers in each row, store with indices, sort, and take first k

Binary Search Optimization — Algorithm Steps

For each row, use binary search to find the first position of 0
The position gives us the count of soldiers (1's before it)
Store soldier count with row index
Sort pairs by soldier count and index
Return first k row indices

Visualization

Tap to expand

Step-by-Step Walkthrough

Binary Search

Find first 0 position using binary search

Count Soldiers

Position gives soldier count

Sort Results

Sort by strength and index

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>

int countSoldiers(int* row, int colSize) {
    int left = 0, right = colSize;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (row[mid] == 1) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

typedef struct {
    int soldiers;
    int index;
} RowStrength;

int compare(const void *a, const void *b) {
    RowStrength *rowA = (RowStrength*)a;
    RowStrength *rowB = (RowStrength*)b;
    if (rowA->soldiers != rowB->soldiers) {
        return rowA->soldiers - rowB->soldiers;
    }
    return rowA->index - rowB->index;
}

int* kWeakestRows(int** mat, int matSize, int* matColSize, int k, int* returnSize) {
    *returnSize = k;
    
    // Count soldiers using binary search and create pairs
    RowStrength* rowsStrength = (RowStrength*)malloc(matSize * sizeof(RowStrength));
    for (int i = 0; i < matSize; i++) {
        int soldierCount = countSoldiers(mat[i], matColSize[i]);
        rowsStrength[i].soldiers = soldierCount;
        rowsStrength[i].index = i;
    }
    
    // Sort by soldier count, then by index
    qsort(rowsStrength, matSize, sizeof(RowStrength), compare);
    
    // Extract first k row indices
    int* result = (int*)malloc(k * sizeof(int));
    for (int i = 0; i < k; i++) {
        result[i] = rowsStrength[i].index;
    }
    
    free(rowsStrength);
    return result;
}

int main() {
    // Parse input and call solution
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m log n + m log m)

O(m log n) for binary search in m rows of length n, O(m log m) for sorting

⚡ Linearithmic

Space Complexity

O(m)

O(m) space to store soldier counts and indices

✓ Linear Space

58.0K Views

Medium Frequency

~15 min Avg. Time

2.1K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler