LeetCode First Month Deck

Як вибрати патерн для задачі?

HashMap → частота, пошук пар, grouping ("two sum", "anagram")
Two Pointers → sorted + pair, O(1) пам'ять, звужувати з двох кінців
Stack → LIFO, matching pairs, O(1) доступ до попереднього/мінімуму
Binary Search → sorted + знайти → O(log n)
Sliding Window → subarray/substring + maximize/minimize

Які ознаки задачі вказують на HashMap?

• Знайти пару або групу за значенням
• Потрібен O(1) пошук або підрахунок
• Слова: duplicate, frequency, count, group, anagram
• Питання: "чи бачив я це значення раніше?"
Складність: O(n) час, O(n) пам'ять

Two Sum #1 — Java шаблон

Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement))
return new int[]{map.get(complement), i};
map.put(nums[i], i);
}
Ключ: зберігаємо value → index, шукаємо complement до додавання

Valid Anagram #242 — Java шаблон (без HashMap)

if (s.length() != t.length()) return false;
int[] count = new int[26];
for (char c : s.toCharArray()) count[c - 'a']++;
for (char c : t.toCharArray()) count[c - 'a']--;
for (int n : count) if (n != 0) return false;
return true;
Типова помилка: забути перевірку довжин на початку

Group Anagrams #49 — Java шаблон

Map<String, List<String>> map = new HashMap<>();
for (String s : strs) {
char[] arr = s.toCharArray();
Arrays.sort(arr);
String key = new String(arr);
map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
}
return new ArrayList<>(map.values());
Ключ: сортований рядок = ключ для анаграм-групи

Які ознаки задачі вказують на Two Pointers?

• Sorted array або рядок
• Знайти пару що задовольняє умову
• O(1) пам'ять вимагається
• Порівняти/обробити елементи з двох кінців
• Питання: "чи можна рухати два кінці назустріч?"
Складність: O(n) час, O(1) пам'ять

Two Pointers: загальний шаблон від обох кінців (Java)

int left = 0, right = n - 1;
while (left < right) {
if (умова виконана) {
// обробити
left++; right--;
} else if (потрібно більше) {
left++;
} else {
right--;
}
}

Container With Most Water #11 — Java шаблон

int left = 0, right = height.length - 1;
int maxWater = 0;
while (left < right) {
int water = Math.min(height[left], height[right]) * (right - left);
maxWater = Math.max(maxWater, water);
if (height[left] < height[right]) left++;
else right--;
}
return maxWater;
Ключ: рухаємо меншу стінку (більша визначає обмеження)

3Sum #15 — Java шаблон з dedup

Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i-1]) continue; // ← dedup 1: outer
int left = i + 1, right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
res.add(Arrays.asList(nums[i], nums[left], nums[right]));
while (left < right && nums[left] == nums[left+1]) left++; // ← dedup 2
while (left < right && nums[right] == nums[right-1]) right--; // ← dedup 3
left++; right--;
} else if (sum < 0) left++;
else right--;
}
}
return res;

3Sum #15 — скільки кроків dedup і де вони стоять?

3 кроки dedup:
1. Outer: if (i > 0 && nums[i] == nums[i-1]) continue
→ на початку for-циклу
2. Inner left: while (left < right && nums[left] == nums[left+1]) left++
3. Inner right: while (left < right && nums[right] == nums[right-1]) right--
→ після res.add(...), ДО фінальних left++ right--
❌ Забути кроки 2 або 3 → дублікати в результаті

Backspace Compare #844 — Java шаблон O(1) пам'ять

int i = s.length() - 1, j = t.length() - 1;
int skipS = 0, skipT = 0;
while (i >= 0 || j >= 0) {
while (i >= 0 && (s.charAt(i) == '#' || skipS > 0)) {
if (s.charAt(i) == '#') skipS++; else skipS--;
i--;
}
while (j >= 0 && (t.charAt(j) == '#' || skipT > 0)) {
if (t.charAt(j) == '#') skipT++; else skipT--;
j--;
}
if (i >= 0 && j >= 0 && s.charAt(i) != t.charAt(j)) return false;
if ((i >= 0) != (j >= 0)) return false;
i--; j--;
}
return true;

Backspace Compare #844 — критичний edge case

Ситуація: один рядок вичерпано, але в іншому ще є символи
❌ Без перевірки → повернеш true помилково
✅ Перевірка після двох while-петель:
if ((i >= 0) != (j >= 0)) return false;

Приклад: s = "ab#", t = "a"
Після обробки: s→'a', t→'a' але довжини різні після '#'

Які ознаки задачі вказують на Stack?

• Matching pairs (дужки, теги HTML)
• "Validity" перевірка вкладених структур
• Last In First Out логіка
• O(1) доступ до попереднього або мінімального елемента
• Питання: "чи важливий порядок LIFO?"
Складність: зазвичай O(n) час, O(n) пам'ять

Valid Parentheses #20 — Java шаблон

Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else {
if (stack.isEmpty()) return false;
char top = stack.pop();
if (c == ')' && top != '(') return false;
if (c == ']' && top != '[') return false;
if (c == '}' && top != '{') return false;
}
}
return stack.isEmpty();
Типова помилка: забути return stack.isEmpty() (незакриті дужки!)

Min Stack #155 — Java шаблон (два стеки)

Stack<Integer> stack = new Stack<>();
Stack<Integer> minStack = new Stack<>();

void push(int val) {
stack.push(val);
if (minStack.isEmpty() || val <= minStack.peek())
minStack.push(val);
}
void pop() {
if (stack.peek().equals(minStack.peek()))
minStack.pop();
stack.pop();
}
int getMin() { return minStack.peek(); }

Min Stack #155 — дві типові помилки

❌ Помилка 1: val < minStack.peek() замість val <= peek()
→ при рівних елементах: push(3), push(3), pop()
minStack стає порожнім, але мін має бути 3
❌ Помилка 2: stack.peek() == minStack.peek() (для Integer!)
→ порівняння посилань, не значень
✅ Правильно: stack.peek().equals(minStack.peek())
Правило: pop з minStack ТІЛЬКИ якщо top == поточний мінімум

Які ознаки задачі вказують на Binary Search?

• Sorted array (відсортований масив)
• Знайти значення або межу → O(log n)
• Слова: "search", "find position", "first bad", "leftmost"
• Питання: "чи можна відкинути половину простору пошуку?"
Складність: O(log n) час, O(1) пам'ять

Binary Search T1 vs T2 — як вибрати?

Template 1: while (left <= right)
→ Знайти ТОЧНЕ значення або позицію вставки
→ Тригери: "знайди X", "search", "insert position"
→ Приклади: #704, #35, #374

Template 2: while (left < right)
→ Знайти МЕЖУ: leftmost, перший поганий, мінімальний що задовольняє
→ Тригери: "first bad", "leftmost", "minimum such that"
→ Приклади: #278, find leftmost, count in sorted

Binary Search Template 1 (exact match) — Java код

int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
else if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
// left = позиція вставки (для Search Insert Position)
return -1;

Binary Search Template 2 (boundary search) — Java код

int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (condition(mid)) right = mid; // ← right = mid (НЕ mid-1!)
else left = mid + 1;
}
// left == right == відповідь
return (check(left)) ? left : -1;
❌ Типова помилка: написати right = mid - 1 → пропустиш відповідь

Binary Search: чому T2 використовує right = mid, а не right = mid - 1?

T1: while (left <= right)
→ mid перевірено і відкинуто → right = mid - 1 безпечно
T2: while (left < right), шукаємо межу
→ mid МОЖЕ бути відповіддю → right = mid зберігає його
→ якщо написати right = mid - 1, відповідь втрачена назавжди
Аналогія T2: "відрізаємо ліво, зберігаємо право"

Count target in sorted array — Java шаблон (T2 chain)

// Step 1: знайти leftmost (T2)
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] >= target) right = mid;
else left = mid + 1;
}
int leftMost = (nums[left] == target) ? left : -1;

// Step 2: якщо не знайдено → 0
if (leftMost == -1) return 0;

// Step 3: рахувати від leftMost
int count = 0;
while (leftMost < nums.length && nums[leftMost] == target) {
count++; leftMost++;
}
return count;

Які ознаки задачі вказують на Sliding Window?

• Subarray або substring (суміжні елементи!)
• Знайти max / min / count
• Fixed: якщо дано розмір k
• Variable: якщо дано умову (без повторень, сума ≤ k)
• Питання: "чи можна додавати/видаляти з країв вікна?"
Складність: O(n) час, O(1) або O(k) пам'ять

Sliding Window Fixed (розмір k) — Java шаблон

int left = 0, sum = 0, maxSum = Integer.MIN_VALUE;
for (int right = 0; right < arr.length; right++) {
sum += arr[right]; // expand
if (right - left + 1 > k) {
sum -= arr[left]; // shrink
left++;
}
if (right - left + 1 == k)
maxSum = Math.max(maxSum, sum);
}
Тригер: "subarray of size k"

Sliding Window Variable (умова) — Java шаблон

int left = 0, maxLen = 0;
for (int right = 0; right < arr.length; right++) {
// expand: додай arr[right] до вікна
while (/* вікно порушує умову */) {
// shrink: видали arr[left] зі структури
left++;
}
maxLen = Math.max(maxLen, right - left + 1);
}
❌ Типова помилка: не видаляти arr[left] зі структури при звуженні

Longest Substring Without Repeating #3 — Java шаблон

Set<Character> set = new HashSet<>();
int left = 0, maxLen = 0;
for (int right = 0; right < s.length(); right++) {
while (set.contains(s.charAt(right))) {
set.remove(s.charAt(left));
left++;
}
set.add(s.charAt(right));
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
Ключ: HashSet для O(1) перевірки дублікату

Longest Substring #3 — типова помилка при звуженні

❌ Тільки left++ без видалення з HashSet
→ set містить символи яких вже немає у вікні
→ while-умова спрацьовує неправильно
✅ Правильно:
while (set.contains(s.charAt(right))) {
set.remove(s.charAt(left)); // ← обов'язково
left++;
}

Best Time to Buy/Sell Stock #121 — Java шаблон

int minPrice = Integer.MAX_VALUE, maxProfit = 0;
for (int price : prices) {
minPrice = Math.min(minPrice, price);
maxProfit = Math.max(maxProfit, price - minPrice);
}
return maxProfit;
Патерн: greedy (НЕ sliding window!)
Тригер: одна транзакція, maximize profit
Складність: O(n) час, O(1) пам'ять