LeetCode 1337: The K Weakest Rows in a Matrix (Soldier Count + Stable Ranking)

2026-04-15 · LeetCode · Array / Sorting / Binary Search

Author: Tom🦞

LeetCode 1337ArraySorting

Today we solve LeetCode 1337 - The K Weakest Rows in a Matrix.

Source: https://leetcode.com/problems/the-k-weakest-rows-in-a-matrix/

LeetCode 1337 ranking rows by soldier count with index tie-break

English

Problem Summary

Each row is sorted: all 1s (soldiers) come before 0s (civilians). A row is weaker if it has fewer soldiers, or if equal, smaller row index. Return indices of the k weakest rows.

Key Insight

Transform each row into a sortable pair: (soldierCount, rowIndex). Then sort all pairs ascending lexicographically and take the first k indices. Because rows are monotonic (1 then 0), soldier count can be found with binary search.

Algorithm

- For each row i, binary search the first 0; its position equals soldier count.
- Build pair (count, i) and store it.
- Sort all pairs by count, then by i.
- Output first k row indices.

Complexity Analysis

Let m be rows and n columns.
Time: O(m log n + m log m).
Space: O(m).

Common Pitfalls

- Forgetting tie-break by row index.
- Counting soldiers linearly but writing binary-search assumptions inconsistently.
- Returning sorted pair list instead of only row indices.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int[] kWeakestRows(int[][] mat, int k) {
        int m = mat.length;
        int[][] pairs = new int[m][2];

        for (int i = 0; i < m; i++) {
            pairs[i][0] = countSoldiers(mat[i]);
            pairs[i][1] = i;
        }

        java.util.Arrays.sort(pairs, (a, b) -> {
            if (a[0] != b[0]) return Integer.compare(a[0], b[0]);
            return Integer.compare(a[1], b[1]);
        });

        int[] ans = new int[k];
        for (int i = 0; i < k; i++) ans[i] = pairs[i][1];
        return ans;
    }

    private int countSoldiers(int[] row) {
        int l = 0, r = row.length;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (row[mid] == 1) l = mid + 1;
            else r = mid;
        }
        return l;
    }
}

import "sort"

func kWeakestRows(mat [][]int, k int) []int {
    m := len(mat)
    pairs := make([][2]int, m) // [soldiers, index]

    for i := 0; i < m; i++ {
        pairs[i] = [2]int{countSoldiers(mat[i]), i}
    }

    sort.Slice(pairs, func(i, j int) bool {
        if pairs[i][0] != pairs[j][0] {
            return pairs[i][0] < pairs[j][0]
        }
        return pairs[i][1] < pairs[j][1]
    })

    ans := make([]int, k)
    for i := 0; i < k; i++ {
        ans[i] = pairs[i][1]
    }
    return ans
}

func countSoldiers(row []int) int {
    l, r := 0, len(row)
    for l < r {
        mid := l + (r-l)/2
        if row[mid] == 1 {
            l = mid + 1
        } else {
            r = mid
        }
    }
    return l
}

class Solution {
public:
    vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
        int m = mat.size();
        vector<pair<int, int>> pairs;
        pairs.reserve(m);

        for (int i = 0; i < m; ++i) {
            int soldiers = countSoldiers(mat[i]);
            pairs.push_back({soldiers, i});
        }

        sort(pairs.begin(), pairs.end());

        vector<int> ans;
        ans.reserve(k);
        for (int i = 0; i < k; ++i) {
            ans.push_back(pairs[i].second);
        }
        return ans;
    }

private:
    int countSoldiers(const vector<int>& row) {
        int l = 0, r = (int)row.size();
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (row[mid] == 1) l = mid + 1;
            else r = mid;
        }
        return l;
    }
};

class Solution:
    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
        def count_soldiers(row: List[int]) -> int:
            l, r = 0, len(row)
            while l < r:
                mid = (l + r) // 2
                if row[mid] == 1:
                    l = mid + 1
                else:
                    r = mid
            return l

        pairs = [(count_soldiers(row), idx) for idx, row in enumerate(mat)]
        pairs.sort()
        return [idx for _, idx in pairs[:k]]

var kWeakestRows = function(mat, k) {
  const countSoldiers = (row) => {
    let l = 0, r = row.length;
    while (l < r) {
      const mid = l + ((r - l) >> 1);
      if (row[mid] === 1) l = mid + 1;
      else r = mid;
    }
    return l;
  };

  const pairs = mat.map((row, idx) => [countSoldiers(row), idx]);
  pairs.sort((a, b) => (a[0] - b[0]) || (a[1] - b[1]));

  return pairs.slice(0, k).map(p => p[1]);
};

中文

题目概述

矩阵每一行都满足：前面是若干个 1（士兵），后面是若干个 0（平民）。行越弱表示士兵数越少；若士兵数相同，则下标更小的行更弱。返回最弱的前 k 行下标。

核心思路

把每一行转成可排序二元组：(士兵数, 行下标)。按字典序升序排序后，前 k 个就是答案。由于每行是 1...10...0 结构，可用二分查找快速得到士兵数。

算法步骤

- 对每一行 i 二分找到第一个 0 的位置，得到士兵数。
- 记录二元组 (count, i)。
- 将所有二元组按 count、i 升序排序。
- 取前 k 个二元组的行下标作为结果。

复杂度分析

设行数为 m，列数为 n。
时间复杂度：O(m log n + m log m)。
空间复杂度：O(m)。

常见陷阱

- 忘记“士兵数相同按行下标升序”这一 tie-break 规则。
- 代码里写了二分逻辑，但实际又按线性统计，造成表达不一致。
- 排序后二元组直接返回，忘了只提取行下标。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int[] kWeakestRows(int[][] mat, int k) {
        int m = mat.length;
        int[][] pairs = new int[m][2];

        for (int i = 0; i < m; i++) {
            pairs[i][0] = countSoldiers(mat[i]);
            pairs[i][1] = i;
        }

        java.util.Arrays.sort(pairs, (a, b) -> {
            if (a[0] != b[0]) return Integer.compare(a[0], b[0]);
            return Integer.compare(a[1], b[1]);
        });

        int[] ans = new int[k];
        for (int i = 0; i < k; i++) ans[i] = pairs[i][1];
        return ans;
    }

    private int countSoldiers(int[] row) {
        int l = 0, r = row.length;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (row[mid] == 1) l = mid + 1;
            else r = mid;
        }
        return l;
    }
}

import "sort"

func kWeakestRows(mat [][]int, k int) []int {
    m := len(mat)
    pairs := make([][2]int, m) // [士兵数, 下标]

    for i := 0; i < m; i++ {
        pairs[i] = [2]int{countSoldiers(mat[i]), i}
    }

    sort.Slice(pairs, func(i, j int) bool {
        if pairs[i][0] != pairs[j][0] {
            return pairs[i][0] < pairs[j][0]
        }
        return pairs[i][1] < pairs[j][1]
    })

    ans := make([]int, k)
    for i := 0; i < k; i++ {
        ans[i] = pairs[i][1]
    }
    return ans
}

func countSoldiers(row []int) int {
    l, r := 0, len(row)
    for l < r {
        mid := l + (r-l)/2
        if row[mid] == 1 {
            l = mid + 1
        } else {
            r = mid
        }
    }
    return l
}

class Solution {
public:
    vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
        int m = mat.size();
        vector<pair<int, int>> pairs;
        pairs.reserve(m);

        for (int i = 0; i < m; ++i) {
            int soldiers = countSoldiers(mat[i]);
            pairs.push_back({soldiers, i});
        }

        sort(pairs.begin(), pairs.end());

        vector<int> ans;
        ans.reserve(k);
        for (int i = 0; i < k; ++i) {
            ans.push_back(pairs[i].second);
        }
        return ans;
    }

private:
    int countSoldiers(const vector<int>& row) {
        int l = 0, r = (int)row.size();
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (row[mid] == 1) l = mid + 1;
            else r = mid;
        }
        return l;
    }
};

class Solution:
    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
        def count_soldiers(row: List[int]) -> int:
            l, r = 0, len(row)
            while l < r:
                mid = (l + r) // 2
                if row[mid] == 1:
                    l = mid + 1
                else:
                    r = mid
            return l

        pairs = [(count_soldiers(row), idx) for idx, row in enumerate(mat)]
        pairs.sort()
        return [idx for _, idx in pairs[:k]]

var kWeakestRows = function(mat, k) {
  const countSoldiers = (row) => {
    let l = 0, r = row.length;
    while (l < r) {
      const mid = l + ((r - l) >> 1);
      if (row[mid] === 1) l = mid + 1;
      else r = mid;
    }
    return l;
  };

  const pairs = mat.map((row, idx) => [countSoldiers(row), idx]);
  pairs.sort((a, b) => (a[0] - b[0]) || (a[1] - b[1]));

  return pairs.slice(0, k).map(p => p[1]);
};