Поиск в отсортированной матрице: Search a 2D Matrix I и II, k-й наименьший

Как искать в отсортированной матрице: бинпоиск по «развёрнутому» массиву, поиск от угла лесенкой за O(m+n) и k-й наименьший элемент через бинпоиск по ответу. Код на Python.

15 мин чтенияалгоритмы · бинарный поиск · матрицы · python

Коротко

ЗадачаКак отсортирована матрицаПриёмВремя
Search a 2D Matrix (LeetCode 74)строки по возрастанию, каждая строка начинается больше, чем кончилась предыдущаяобычный бинпоиск по индексу 0..mn−10..mn-1O(log⁡(mn))O(\log(mn))
Search a 2D Matrix II (LeetCode 240)строки и столбцы по возрастанию, порядка между строками нетлесенка от правого верхнего углаO(m+n)O(m + n)
Kth Smallest Element in a Sorted Matrix (LeetCode 378)как в задаче 240, матрица n×nn \times nбинпоиск по значению + подсчёт лесенкойO(nlog⁡(max⁡−min⁡))O(n \log(\max - \min))
  • Сначала выясните, какая сортировка у матрицы. От этого зависит всё решение, и это первый вопрос, который стоит задать интервьюеру.
  • Матрица из задачи 74 — это просто отсортированный массив, разрезанный на строки. Ищем в ней как в массиве.
  • В матрице из задачи 240 из правого верхнего угла каждое сравнение отбрасывает целую строку или целый столбец.
  • Та же лесенка за O(n)O(n) считает, сколько элементов не больше xx. Отсюда k-й наименьший через бинпоиск по ответу.

Два вида «отсортированных» матриц

Фраза «матрица отсортирована» на собеседовании может значить разное. Сравните:

Задача 74                 Задача 240
 1   3   5   7             1   4   7  11  15
10  11  16  20             2   5   8  12  19
23  30  34  60             3   6   9  16  22
                          10  13  14  17  24
                          18  21  23  26  30

Слева, если читать построчно, получится сплошной отсортированный массив: 1 3 5 7 10 11 …. Справа каждая строка и каждый столбец возрастают, но строки перекрываются: во второй строке есть 2, хотя первая доходит до 15. Построчно такая матрица не отсортирована.

Решение для правой матрицы работает и для левой, но медленнее, чем могло бы. Решение для левой на правой просто ломается. Поэтому спросите, гарантировано ли, что первый элемент строки больше последнего элемента предыдущей.

Search a 2D Matrix: матрица как один массив

Условие: матрица m×nm \times n, строки отсортированы, первый элемент каждой строки больше последнего элемента предыдущей. Есть ли в ней target?

Перебор и бинпоиск по строкам

Перебор всех клеток — O(mn)O(mn), он не использует сортировку вообще. Бинарный поиск в каждой строке — O(mlog⁡n)O(m \log n), уже лучше, но тоже не оптимально: мы игнорируем порядок между строками.

Бинпоиск по виртуальному массиву

Пронумеруем клетки построчно: клетка (r, c) получает индекс r * n + c. Обратное преобразование: индекс i — это строка i // n и столбец i % n. По условию значения по этим индексам идут по возрастанию, значит работает обычный бинарный поиск на отрезке [0,mn−1][0, mn - 1], только вместо arr[mid] читаем клетку матрицы.

def search_matrix_1(matrix, target): if not matrix or not matrix[0]: return False rows, cols = len(matrix), len(matrix[0]) lo, hi = 0, rows * cols - 1 while lo <= hi: mid = (lo + hi) // 2 value = matrix[mid // cols][mid % cols] if value == target: return True if value < target: lo = mid + 1 else: hi = mid - 1 return False m = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]] print(search_matrix_1(m, 3)) # True print(search_matrix_1(m, 13)) # False

Время O(log⁡(mn))=O(log⁡m+log⁡n)O(\log(mn)) = O(\log m + \log n), память O(1)O(1). Матрицу никуда не копируем: «развёрнутый» массив существует только в формуле индекса.

Самая частая ошибка здесь — делить на число строк вместо числа столбцов: mid // rows. На квадратной матрице тесты проходят, на прямоугольной — нет. Строка индекса определяется тем, сколько полных строк длины cols до него поместилось.

Вариант: два бинпоиска

Можно рассуждать иначе: сначала бинпоиском по первому столбцу найти последнюю строку, которая начинается с числа не больше target, потом бинпоиском искать в ней.

from bisect import bisect_left, bisect_right def search_matrix_1_two_steps(matrix, target): if not matrix or not matrix[0]: return False
# первый столбец: ищем последнюю строку, которая начинается с <= target
first = [row[0] for row in matrix]
r = bisect_right(first, target) - 1
if r < 0:
    return False
row = matrix[r]
c = bisect_left(row, target)
return c < len(row) and row[c] == target

Асимптотика та же: $O(\log m + \log n)$. Строчка `first = [...]` в этой версии стоит $O(m)$ — для чистоты можно искать по первому столбцу вручную, без копирования. Плюс этого варианта в том, что он естественно обобщается на случай, когда строки разной длины: развернуть такую матрицу в один индекс уже не получится.

## Search a 2D Matrix II: поиск лесенкой

Условие: каждая строка возрастает слева направо, каждый столбец — сверху вниз. Есть ли в матрице `target`?

Развернуть в массив больше нельзя. Бинпоиск по каждой строке даёт $O(m \log n)$. Есть решение проще и быстрее.

### Почему правый верхний угол

Посмотрим на правый верхний элемент `15`. Он **самый большой в своей строке** и **самый маленький в своём столбце**. Это единственный угол (вместе с левым нижним) с таким свойством, и именно оно даёт однозначное решение на каждом шаге:

- если `matrix[r][c] > target`, то весь столбец `c` ниже текущей клетки ещё больше. Столбец можно выбросить: `c -= 1`;
- если `matrix[r][c] < target`, то вся строка `r` левее текущей клетки ещё меньше. Строку можно выбросить: `r += 1`;
- если равно — нашли.

Из левого верхнего угла так не получится: там элемент меньше всех и в строке, и в столбце. Если он меньше `target`, непонятно, куда идти — вправо или вниз. Так же бесполезен правый нижний угол.

```python
def search_matrix_2(matrix, target):
    if not matrix or not matrix[0]:
        return False
    r, c = 0, len(matrix[0]) - 1  # правый верхний угол
    while r < len(matrix) and c >= 0:
        value = matrix[r][c]
        if value == target:
            return True
        if value > target:
            c -= 1  # весь столбец c ниже ещё больше
        else:
            r += 1  # вся строка r левее ещё меньше
    return False


m = [
    [1, 4, 7, 11, 15],
    [2, 5, 8, 12, 19],
    [3, 6, 9, 16, 22],
    [10, 13, 14, 17, 24],
    [18, 21, 23, 26, 30],
]
print(search_matrix_2(m, 5))   # True
print(search_matrix_2(m, 20))  # False

Разбор: ищем 14

ШагКлеткаЗначениеРешение
1(0, 4)1515 > 14, выбрасываем столбец 4
2(0, 3)1111 < 14, выбрасываем строку 0
3(1, 3)1212 < 14, выбрасываем строку 1
4(2, 3)1616 > 14, выбрасываем столбец 3
5(2, 2)99 < 14, выбрасываем строку 2
6(3, 2)14нашли

Путь идёт лесенкой: только влево и вниз. Отсюда и название — staircase search.

Почему это корректно и сколько стоит

Инвариант: если target есть в матрице, он лежит в прямоугольнике «строки от r до конца, столбцы от 0 до c». В начале это вся матрица. Каждый шаг выбрасывает строку или столбец, в которых target быть не может, — это мы показали выше. Когда прямоугольник опустел (r == m или c < 0), элемента нет.

На каждом шаге либо r растёт, либо c уменьшается. Всего шагов не больше m+n−1m + n - 1, время O(m+n)O(m + n), память O(1)O(1).

Сравним с бинпоиском по строкам. Для квадратной матрицы 1000×10001000 \times 1000 лесенка делает до 2000 шагов, бинпоиск по строкам — около 1000⋅10=10 0001000 \cdot 10 = 10\,000 сравнений. Но если матрица очень вытянутая, например 10×1 000 00010 \times 1\,000\,000, бинпоиск по 10 строкам даёт около 200 сравнений, а лесенка может пройти миллион шагов. На собеседовании стоит упомянуть: «для квадратной матрицы лесенка лучше, для сильно вытянутой — бинпоиск по коротким строкам». Это хороший сигнал, что вы думаете о входных данных, а не заучили ответ.

Для квадратной n×nn \times n матрицы быстрее O(n)O(n) в худшем случае нельзя: все nn элементов побочной диагонали могут быть никак не связаны между собой порядком, и каждый придётся проверить.

То же решение на JavaScript:

function searchMatrix(matrix, target) { if (matrix.length === 0 || matrix[0].length === 0) return false let r = 0 let c = matrix[0].length - 1 while (r < matrix.length && c >= 0) { const value = matrix[r][c] if (value === target) return true if (value > target) c-- else r++ } return false }

Где ещё работает лесенка

Лесенка — это по сути два указателя, только по двум измерениям матрицы. Она подходит всюду, где нужно посчитать или найти что-то относительно порога.

Count Negative Numbers in a Sorted Matrix (LeetCode 1351): матрица не возрастает по строкам и столбцам, посчитать отрицательные. Идём из левого нижнего угла. Если клетка отрицательная, отрицательны и все клетки правее неё в этой строке: прибавляем их число и поднимаемся. Иначе сдвигаемся вправо.

def count_negatives(grid): rows, cols = len(grid), len(grid[0]) r, c = rows - 1, 0 total = 0 while r >= 0 and c < cols: if grid[r][c] < 0: total += cols - c r -= 1 else: c += 1 return total print(count_negatives([[4, 3, 2, -1], [3, 2, 1, -1], [1, 1, -1, -2], [-1, -1, -2, -3]])) # 8

Это O(m+n)O(m + n) вместо O(mn)O(mn) перебора. Самая полезная разновидность лесенки — подсчёт элементов, не превосходящих xx. На ней держится следующая задача.

K-й наименьший элемент в отсортированной матрице

Условие LeetCode 378: квадратная матрица n×nn \times n, строки и столбцы отсортированы по возрастанию. Найти k-й по величине элемент в порядке сортировки (с повторами, а не k-й различный).

 1   5   9
10  11  13      k = 8  →  13
12  13  15

Все элементы по порядку: 1 5 9 10 11 12 13 13 15. Восьмой — 13.

Решение 1: собрать и отсортировать

Сложить все n2n^2 элементов в список и отсортировать — O(n2log⁡n)O(n^2 \log n) времени и O(n2)O(n^2) памяти. Работает, но не использует структуру матрицы, а условие задачи прямо просит память лучше O(n2)O(n^2).

Решение 2: куча, как в слиянии k списков

Каждая строка — отсортированный список. Значит, это задача слияния k отсортированных списков: кладём в кучу первые элементы строк, k−1k-1 раз достаём минимум и добавляем следующий элемент той же строки.

import heapq def kth_smallest_heap(matrix, k): n = len(matrix) heap = [(matrix[r][0], r, 0) for r in range(min(n, k))] heapq.heapify(heap) for _ in range(k - 1): value, r, c = heapq.heappop(heap) if c + 1 < n: heapq.heappush(heap, (matrix[r][c + 1], r, c + 1)) return heap[0][0] print(kth_smallest_heap([[1, 5, 9], [10, 11, 13], [12, 13, 15]], 8)) # 13

Строк больше kk брать не нужно: k-й элемент заведомо найдётся среди первых kk строк. Время O(n+klog⁡min⁡(n,k))O(n + k \log \min(n, k)), память O(min⁡(n,k))O(\min(n, k)). При kk порядка n2n^2 это O(n2log⁡n)O(n^2 \log n) — не лучше сортировки по времени, но память уже O(n)O(n).

Решение 3: бинпоиск по ответу

Вместо того чтобы искать позицию, будем искать значение. Обозначим cnt(x)\text{cnt}(x) — сколько элементов матрицы не больше xx. Эта функция не убывает по xx. Ответ — наименьшее xx, при котором cnt(x)≥k\text{cnt}(x) \ge k.

Монотонный предикат на отрезке значений — классическая постановка бинпоиска по ответу. Ищем на отрезке [matrix[0][0],matrix[n−1][n−1]][\text{matrix}[0][0], \text{matrix}[n-1][n-1]]: это минимум и максимум матрицы.

Осталось быстро считать cnt(x)\text{cnt}(x). Это та же лесенка, только из левого нижнего угла:

  • если matrix[r][c] <= x, то и все элементы столбца c выше него не больше x. Прибавляем r + 1 и идём вправо;
  • иначе этот элемент и всё правее в строке больше x. Поднимаемся на строку вверх.
def count_less_equal(matrix, x): n = len(matrix) r, c = n - 1, 0 # левый нижний угол count = 0 while r >= 0 and c < n: if matrix[r][c] <= x: count += r + 1 # весь столбец c до строки r включительно c += 1 else: r -= 1 return count def kth_smallest(matrix, k): lo, hi = matrix[0][0], matrix[-1][-1] while lo < hi: mid = (lo + hi) // 2 if count_less_equal(matrix, mid) >= k: hi = mid else: lo = mid + 1 return lo print(kth_smallest([[1, 5, 9], [10, 11, 13], [12, 13, 15]], 8)) # 13

Разбор на примере

Матрица выше, k=8k = 8, отрезок [1,15][1, 15].

lohimidcnt(mid)\text{cnt}(\text{mid})Решение
11582 (1, 5)2<82 < 8, lo = 9
915126 (1, 5, 9, 10, 11, 12)6<86 < 8, lo = 13
13151488≥88 \ge 8, hi = 14
13141388≥88 \ge 8, hi = 13

lo == hi == 13 — ответ.

Почему ответ обязательно есть в матрице

Частый вопрос интервьюера: мы перебираем значения из отрезка, а не элементы матрицы. Вдруг найдём число, которого в матрице нет?

Не найдём. Бинпоиск возвращает наименьшее xx с cnt(x)≥k\text{cnt}(x) \ge k. Пусть xx не встречается в матрице. Тогда элементов, не больших xx, ровно столько же, сколько не больших x−1x - 1: cnt(x−1)=cnt(x)≥k\text{cnt}(x - 1) = \text{cnt}(x) \ge k. Значит, xx не наименьшее — противоречие. Для целых чисел этого достаточно.

Если в матрице дробные числа, бинпоиск по значению тоже работает, но остановить его надо по точности, а ответ потом «прижать» к ближайшему элементу матрицы, не превосходящему найденное значение. На LeetCode матрица целочисленная, так что этот случай обычно не спрашивают.

Сложность

Подсчёт — O(n)O(n) (лесенка на 2n2n шагов). Бинпоиск делает O(log⁡(max⁡−min⁡))O(\log(\max - \min)) итераций. Итого O(nlog⁡(max⁡−min⁡))O(n \log(\max - \min)) времени и O(1)O(1) памяти. При значениях до 10910^9 это около 30 проходов лесенки — для n=300n = 300 меньше 20 000 операций против полутора миллионов у сортировки.

Существует и алгоритм Фредериксона–Джонсона, который находит k-й элемент в такой матрице за O(n)O(n), но на собеседованиях его не ждут: он заметно сложнее и почти не встречается в разборах.

Та же идея без матрицы

Kth Smallest Number in Multiplication Table (LeetCode 668): таблица умножения m×nm \times n, где в клетке (i,j)(i, j) стоит i⋅ji \cdot j. Хранить её не нужно: строка ii — это числа i,2i,…,nii, 2i, \ldots, ni, и в ней не больше xx ровно min⁡(⌊x/i⌋,n)\min(\lfloor x / i \rfloor, n) элементов.

def find_kth_number(m, n, k): lo, hi = 1, m * n while lo < hi: mid = (lo + hi) // 2 count = sum(min(mid // i, n) for i in range(1, m + 1)) if count >= k: hi = mid else: lo = mid + 1 return lo print(find_kth_number(3, 3, 5)) # 3

Время O(mlog⁡(mn))O(m \log(mn)). Тот же каркас решает Find K-th Smallest Pair Distance (LeetCode 719): сортируем массив, а пары с расстоянием не больше xx считаем двумя указателями.

Сводная таблица

ЗадачаНаивноОптимальноПамять
74, строки «продолжают» друг другаO(mn)O(mn)O(log⁡(mn))O(\log(mn)), бинпоиск по индексуO(1)O(1)
240, строки и столбцы отсортированыO(mn)O(mn)O(m+n)O(m + n), лесенкаO(1)O(1)
1351, подсчёт отрицательныхO(mn)O(mn)O(m+n)O(m + n), лесенкаO(1)O(1)
378, k-й наименьшийO(n2log⁡n)O(n^2 \log n)O(nlog⁡(max⁡−min⁡))O(n \log(\max - \min)), бинпоиск + лесенкаO(1)O(1)
668, таблица умноженияO(mnlog⁡(mn))O(mn \log(mn))O(mlog⁡(mn))O(m \log(mn))O(1)O(1)

Типичные ошибки

  1. Решение задачи 74 на матрице из задачи 240. Бинпоиск по развёрнутому индексу на матрице, где строки перекрываются, пропустит элементы. Сначала уточните условие.
  2. mid // rows вместо mid // cols. На квадратных тестах ошибка не видна.
  3. Лесенка из левого верхнего угла. Оттуда нет однозначного хода. Только правый верхний или левый нижний.
  4. Пустая матрица. [] и [[]] — разные случаи: во втором len(matrix[0]) равен нулю, и c стартует с -1. Проверка if not matrix or not matrix[0] закрывает оба.
  5. count > k вместо count >= k в бинпоиске по ответу. При повторяющихся значениях (две 13 в примере) получится ответ больше правильного. Ищем наименьшее xx, при котором элементов не меньше kk.
  6. Возврат mid вместо lo. В шаблоне while lo < hi ответ — это lo после выхода из цикла.
  7. Переполнение (lo + hi) / 2 в Java и C++ при отрицательных и больших значениях. Пишите lo + (hi - lo) / 2. В Python проблемы нет, но про неё полезно сказать вслух.

Как подавать на собеседовании

  1. Уточните тип сортировки матрицы и размеры: квадратная ли, бывают ли пустые строки, есть ли повторы.
  2. Назовите перебор за O(mn)O(mn) одной фразой и сразу переходите к структуре.
  3. Для задачи 74 скажите «это отсортированный массив, нарезанный на строки» и напишите бинпоиск с формулой индекса.
  4. Для задачи 240 объясните, почему именно правый верхний угол: он максимум строки и минимум столбца. Затем инвариант и оценка O(m+n)O(m + n).
  5. Для k-го наименьшего начните с кучи — её легко написать и легко обосновать. Затем предложите бинпоиск по значению и объясните, почему ответ всегда элемент матрицы.

Близкие темы на сайте: поиск в повёрнутом отсортированном массиве — ещё одна задача, где бинпоиск работает на «почти» отсортированных данных, и спиральный обход матрицы, если нужно потренировать аккуратную работу с индексами.

Потренироваться в спокойной обстановке

Все задачи