Як підходити до задачі — Структури даних і алгоритми

На LeetCode і на співбесідах перемагає не «знати всі задачі», а системний підхід: зрозуміти умову, спробувати наївний перебір, прочитати обмеження і обрати патерн. Досвідчений розробник не вгадує «магічний трюк» — він проходить однаковий чекліст для кожної нової задачі, навіть якщо тема незнайома.

Час на задачу варто ділити: перші пʼять хвилин — розуміння і приклади; наступні десять — наївний перебір і оцінка складності; решта — оптимізація і код. Якщо за пʼятнадцять хвилин оптимальне рішення не зʼявилось — реалізуйте повільне, але правильне, і лише потім покращуйте. Частковий бал кращий за зависання перед порожнім екраном.

Крок 1: перефразувати задачу

Прочитайте умову двічі. Своїми словами: що на вході, що на виході, чи можуть бути дублікати, чи масив відсортований, чи дозволено змінювати вхід. Запишіть 1–2 приклади руками — граничні випадки (порожній масив, один елемент). Якщо умова каже «поверни індекси» — не повертайте значення; якщо «унікальна відповідь гарантована» — не тратьте час на перевірку кількох розвʼязків, але все одно подумайте про формат виходу.

Порада

Корисні питання до себе: чи можу відсортувати вхід без шкоди для задачі? Чи потрібен суцільний підмасив, чи будь-яка підмножина? Чи є відʼємні числа? Чи ціль може бути нулем? Відповіді часто одразу відсікають половину патернів з курсу.

Приклад

«Two Sum»: дано масив чисел і ціль. Знайти два індекси, сума яких дорівнює цілі. Вхід: один розвʼязок гарантовано. Вихід: пара індексів, не значень.

Крок 2: наївний перебір

Наївний перебір — найпростіше рішення, часто повільне, але правильне. Для Two Sum: дві вкладені петлі — $O(n^2)$ . Це база: якщо наївний перебір працює, ви розумієте задачу; далі оптимізуєте. Навіть якщо одразу згадали словник — спочатку проговоріть наївний перебір інтервʼюеру: це показує дисципліну мислення і дає опору, якщо оптимальний підхід забудеться під стресом.

Крок 3: обмеження → патерн

Обмеження під задачею на LeetCode — підказка. $n \le 10^5$ — $O(n^2)$ може не пройти; шукайте $O(n)$ або $O(n \log n)$ . $n \le 20$ — можливий бектрекінг або $O(2^n)$ . Відсортований масив — два вказівники або бінарний пошук.

Порада

Завжди читайте обмеження перед кодом. Типові ліміти: $n \le 10^3$ — $O(n^2)$ підходить; $n \le 10^5$ — потрібен лінійний або $n \log n$ ; $n \le 10^6$ — майже завжди $O(n)$ або $O(\log n)$ на запит.

Типовий фрагмент

Швидка перевірка: чи квадратичний підхід узагалі встигне при даному $n$ .

Python

def likely_ok(n, quadratic=False):
    if quadratic and n > 2000:
        return False
    if n > 10 ** 6:
        return False
    return True

print(likely_ok(10 ** 5, quadratic=True))
print(likely_ok(10 ** 5, quadratic=False))

Вивід

Натисніть «Запустити» — вивід зʼявиться тут

Практика на платформі

Окремої задачі під цей урок немає — мета навчити чекліст. Тренуйте підхід на каталозі Easy.

Каталог задач на LeetCodeФільтр Easy + потрібний тег