🔴Hard
37. Sudoku Solver

Company: 🔍📕📱

📝Напишите алгоритм, который решает головоломку Судоку, заполняя все пустые клетки.

Игровое поле представлено в виде двумерного массива символов, где каждая клетка содержит либо цифру '1'–'9', либо символ '.', обозначающий пустую клетку.

Условия решения:
▫В каждой строке — все цифры 1–9 без повторов
▫В каждом столбце — все цифры 1–9 без повторов
▫В каждом блоке 3×3 — все цифры 1–9 без повторов

💡: при размещении числа, сразу исключайте его из строки, столбца и блока, чтобы сократить поиск

#leetcode37 | #hard #backtracking

➡️ Стартуем тему графов

Представь большую карту страны:
▫Граф — это как схема всех дорог страны
▫Вершина графа — город на карте
▫Ребро графа — дорога между городами

➖Вес ребра — может быть расстоянием в километрах, временем в пути или стоимостью билета
➖Направленные рёбра — если дорога односторонняя
➖Ненаправленные рёбра — обычная дорога, по которой можно ездить в обе стороны

С таким графом можно:
▫Найти кратчайший путь между городами (как в навигаторе)
▫Определить, можно ли проехать из одного города в другой (проверить связность)
▫Построить маршрут, который проходит через все нужные города

🟦Основные алгоритмы для обхода графов это DFS и BFS

✅ DFS (Depth-first search)
Ты путешествуешь вглубь, сначала исследуешь одну ветку дорог до конца, а потом возвращаешься:

🟪Начинаешь с первого города
🟪Выбираешь первую дорогу, которая ведёт куда-то ещё и едешь туда
🟪В новом городе снова выбираешь первую доступную дорогу и так, пока не приедешь в тупик или в город, в котором уже был
🟪Если упёрся — возвращаешься назад в предыдущий город и пробуешь другую дорогу

✅ BFS (Breadth-first search)
Ты путешествуешь по слоям, сначала посещая все города поближе, потом всё дальше и дальше:

▫Начинаешь с первого города
▫Сначала смотришь все соседние города и отмечаешь их, как «следующие в очереди»
▫Затем посещаешь все города на расстоянии 1 дороги, потом на расстоянии 2 дорог, потом 3 и так далее

#graphs

🟢Easy
1971. Find if Path Exists in Graph

Company: 🔍📱📱

📝Дан граф с n вершинами, где каждая вершина помечена от 0 до n-1.

Ребра графа представлены двумерным массивом целых чисел edges, где edges[i] обозначает двунаправленное ребро между вершинами. Каждая пара вершин соединена не более чем одним ребром, и ни одна вершина не имеет ребра, ведущего в себя.

Верните true, если существует допустимый путь от вершины source к вершине destination

💡: используйте Map для удобного представления графа

#leetcode1971 | #easy #graphs

✅ Решение задачи 1971

Time: O(n + m)
Space: O(n + m)

💡 Идея
🟦В начале создаем удобное представление графа в виде Map(вершина—список соседей), просто проходя по заданному массиву вершин и для каждой пары добавляя в Map ребро в обе стороны

🟦Когда граф построен, можно использовать классический поиск в глубину (dfs), чтобы проверить доступность destination от исходного узла source:
▫Помечаем вершину как посещённую, чтобы не зациклиться
▫Рекурсивно идём во все смежные не посещённые вершины, вызывая метод dfs для текущего соседа
▫Если хотя бы один путь привёл к destination, возвращаем true, иначе после обхода всех соседей возвращаем false

👩‍💻 Java Algo | #solution1971

🟢Easy
1791. Find Center of Star Graph

Company: 🔍📱📕

📝Дан неориентированный звёздчатый граф, состоящий из n узлов, помеченных от 1 до n. Верните центр заданного звёздного графа.

Граф представлен двумерным массивом целых чисел edges, где edges[i] указывает на ребро между вершинами.

Ограничения:

3 <= n <= 10^5
edges.length == n - 1

💡: используйте главную особенность центра графа

#leetcode1791 | #easy #graphs

✅ Решение задачи 1791

Time: O(1)
Space: O(1)

💡 Идея
🟦В начале может показаться хорошей идеей построить граф с помощью Map, как в этой задаче, а затем просто пройтись по нему и найти вершину, у которой n-1 соседей, но есть решение получше

🟦Важно заметить главную особенность, которая определяет центр графа — он присутствует в каждом ребре

🟦Используя это, просто проверяем любые два ребра из списка, общая вершина и будет являться центром. Это работает, поскольку в звёздчатом графе с n-1 ребрами только центральный узел имеет степень больше 1

👩‍💻 Java Algo | #solution1791

🟡Medium
886. Possible Bipartition

Company: 📕✴️📱

📝Дано число n и массив dislikes, где dislikes[i] = [aᵢ, bᵢ] — пары людей, которые не ладят между собой.

Верните true, если можно разделить всех n человек на две группы так, чтобы ни одна пара из dislikes не оказалась в одной группе

💡: используйте алгоритмы обхода, чтобы поочерёдно назначать людям противоположные группы и выявлять возможные конфликты

#leetcode886 | #medium #graphs

✅ Решение задачи 886

Time: O(n + m)
Space: O(n + m)

💡 Идея
🟦Мы знаем, что можно построить граф отношений людей, где каждая вершина — это человек, а ребро между двумя вершинами означает, что эти люди не ладят. Наша цель — проверить, можно ли разделить всех на две группы так, чтобы ни одна пара, соединённая ребром, не оказалась вместе

🟦Для этого просто обходим граф с помощью dfs и раскидываем людей по разным группам:
▫Для текущего узла назначаем номер группы (например 1)
▫Далее проходим по всем его соседям и в рекурсивном вызове функции меняем номер группы на противоположный (то есть -1)
▫Если во время обхода встречаем человека, который уже состоит в группе, проверяем — совпадает ли она с той, что должна быть по логике. Если нет — возникает конфликт, значит, разделить людей корректно невозможно

🟦Важно выполнить обход для каждого узла, так как граф может состоять из нескольких несвязных частей. Поэтому, если человек ещё не был распределён в группу, запускаем для него dfs отдельно

👩‍💻 Java Algo | #solution886

🟡Medium
210. Course Schedule II

Company: 🚔✴️📱

📝Вам дан массив prerequisites, где prerequisites[i] = [ai, bi] означает, что для прохождения курса ai необходимо сначала пройти курс bi.

Верните порядок курсов, которые необходимо пройти, чтобы закончить их все. Если допустимых ответов несколько, верните любой из них. Если невозможно закончить все курсы, верните пустой массив

💡: помечайте курсы во время обхода, чтобы обнаружить циклы

#leetcode210 | #medium #graphs

✅ Решение задачи 210

Time: O(n + e)
Space: O(n + e)

💡 Идея
🟦Очевидно, что для прохождения всех курсов мы хотим, чтобы не было ситуации, когда для курса A нужно пройти курс B, а для курса B нужно пройти курса A, так можно и не начинать учиться

🟦Поэтому для каждого курса будем проверять отсутствие цикла в ориентированном графе, который представляет из себя Map [курс – необходимые курсы для прохождения]

🟦Для этого используем dfs (обход в глубину):
➖Текущий узел помечаем как посещенный
➖Затем рекурсивно обходим всех его соседей, то есть курсы, которые нужно пройти до текущего
➖Если успешно прошли все необходимые курсы, снимаем пометку посещения и записываем для текущего курса в Map значение null, обозначая, что этот курс уже проверен и не содержит циклов
➖После этого добавляем курс в результат. Благодаря рекурсии порядок формируется корректно — начиная с самого "глубокого" курса и заканчивая тем, который зависит от других

🟦Базовые случаи dfs
➖если узел посещен, возвращаем false – обнаружен цикл
➖если у узла соседи равны null – значит он уже проверен и можно вернуть true

🟦Важно отметить, что при построении графа добавляем для каждого курса пустой список зависимостей, даже если он ни от чего не зависит, чтобы при обходе он также был рассмотрен и попал в итоговый результат

👩‍💻 Java Algo | #solution210

🟡Medium
1136. Parallel Courses

Company: 📕🔍🚖

📝Дано n курсов и список зависимостей relations, где каждая пара [a, b] означает: курс a должен быть пройден до курса b.

За один семестр можно брать любое количество курсов, если все нужные для них предыдущие курсы уже пройдены.

Нужно вернуть минимальное число семестров, чтобы пройти все курсы, или -1, если пройти все курсы невозможно

💡: начните обход с курсов, у которых нет зависимостей, затем освобождайте следующие и так далее

#leetcode1136 | #medium #graphs

✅ Решение задачи 1136

Time: O(E + V)
Space: O(V)

💡 Идея
🟦Так как число курсов заранее известно, будем использовать массив списков для построения ориентированного графа, где каждая вершина указывает на курсы, которые нужно пройти после текущего

🟦Также для удобства посчитаем для каждого курса количество обязательных предварительных — его «входящую степень»

🟦Все курсы, у которых входящая степень 0, можно взять сразу, поэтому кладём их в очередь на прохождение в первом семестре

🟦Далее запускаем обход графа по уровням (BFS), где каждый уровень — это набор курсов, которые можно пройти в один семестр:
➖фиксируем размер очереди, чтобы не выйти за пределы текущего семестра
➖когда «проходим» курс, снимаем зависимость с его последователей
➖если у какого-то курса после этого входящая степень становится нулевой, он добавляется в очередь, так как теперь подходит для следующего семестра

🟦В конце, если мы смогли обработать все курсы, возвращаем количество семестров; если же что-то осталось недоступным, значит существует цикл, и ответ -1

🟦Такой процесс — классический алгоритм Кана для топологической сортировки (упорядочивание вершин так, чтобы каждое ребро шло только вперёд). Он позволяет определить правильный порядок вершин и проверить, есть ли в графе цикл

👩‍💻 Java Algo | #solution1136