Войти Регистрация
Алгоритмы

171. Отсортировать диагонали таблицы

Средняя

Дана матрица grid из m строк и n столбцов. Диагональ — клетки с одинаковой разностью i − j: от левого или верхнего края вниз направо.

Отсортируйте каждую диагональ по возрастанию сверху вниз и верните новую матрицу.

В работе: Таблица загрузки складов по дням: сдвиг на день и на склад даёт диагональ, по ней смотрят тренд.

Пример 1

Ввод
grid = [[3, 3, 1, 1], [2, 2, 1, 2], [1, 1, 1, 2]]
Вывод
[[1, 1, 1, 1], [1, 2, 2, 2], [1, 2, 3, 3]]

Пример из задачи на собеседовании.

Пример 2

Ввод
grid = [[5]]
Вывод
[[5]]

Одна клетка — одна диагональ.

Ограничения

  • 1 ≤ m, n ≤ 500
  • Значения — целые, в том числе 0 и отрицательные
  • Лимит — 2 с на тест (2000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def sort_diagonals(grid):
МатрицаСортировкаХеш-таблицацельO(n log n)

Источник: Яндекс, фронтенд, репозиторий кандидата на GitHub, 2024. Условие пересказано своими словами.