Сложность: medium
Задача: 378. Kth Smallest Element in a Sorted Matrix

Дана матрица размером n x n, где каждая строка и каждый столбец отсортированы в порядке возрастания. Верните k-й наименьший элемент в матрице.
Заметьте, что это k-й наименьший элемент в отсортированном порядке, а не k-й уникальный элемент.
Вы должны найти решение с использованием памяти лучше, чем O(n²).

Пример:

Input: matrix = [[-5]], k = 1
Output: -5

👨‍💻 Алгоритм:

1⃣Инициализировать мин-кучу H. В нашем решении мы будем рассматривать каждую строку как отдельный список. Поскольку столбцы также отсортированы, мы можем рассматривать каждый столбец как отдельный список.

2⃣Взять первые элементы из min(N, K) строк, где N представляет количество строк, и добавить каждый из этих элементов в кучу. Важно знать, к какой строке и столбцу принадлежит элемент, чтобы в дальнейшем перемещаться по соответствующему списку.

3⃣Мин-куча будет содержать тройки информации (значение, строка, столбец). Куча будет упорядочена по значениям, и мы будем использовать номера строк и столбцов для добавления следующего элемента, если текущий элемент будет удален из кучи.

😎 Решение:

class Solution {
    dfs(word, length, visited, dictionary) {
        if (length === word.length) {
            return true;
        }
        if (visited[length]) {
            return false;
        }
        visited[length] = true;
        for (let i = word.length - (length === 0 ? 1 : 0); i > length; i--) {
            if (dictionary.has(word.slice(length, i)) && this.dfs(word, i, visited, dictionary)) {
                return true;
            }
        }
        return false;
    }

    findAllConcatenatedWordsInADict(words) {
        const dictionary = new Set(words);
        const answer = [];
        for (const word of words) {
            const visited = Array(word.length).fill(false);
            if (this.dfs(word, 0, visited, dictionary)) {
                answer.push(word);
            }
        }
        return answer;
    }
}

const solution = new Solution();
const words = ["cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"];
console.log(solution.findAllConcatenatedWordsInADict(words));

Ставь 👍 и забирай 📚 Базу знаний