Common Mistakes & Anti-patterns

Разбор типичных ошибок и антипаттернов в алгоритмических задачах. Учитесь на чужих ошибках!

#1. Ошибки в Two Pointers

#❌ Бесконечный цикл

# Неправильно
while left < right:
    if condition:
        pass  # Забыли двигать указатель!

# Правильно
while left < right:
    if condition:
        left += 1
    else:
        right -= 1

#❌ Неправильное условие выхода

# Для поиска элемента: left <= right
# Для поиска пика/минимума: left < right

#2. Ошибки в Sliding Window

#❌ Забыли обновить ответ

# Неправильно
for right in range(len(s)):
    expand()
    while not valid():
        shrink()
    # Забыли: result = max(result, right - left + 1)

# Правильно
for right in range(len(s)):
    expand()
    while not valid():
        shrink()
    result = max(result, right - left + 1)

#❌ Неправильный порядок операций

# Порядок: Expand → Shrink → Update

#3. Ошибки в Binary Search

#❌ Переполнение mid

# В языках с фиксированными int:
mid = (left + right) // 2  # Может переполниться!

# Правильно:
mid = left + (right - left) // 2

#❌ Бесконечный цикл

# Неправильно
while left < right:
    mid = (left + right) // 2
    if condition(mid):
        left = mid  # Зацикливание!

# Правильно
while left < right:
    mid = left + (right - left) // 2
    if condition(mid):
        left = mid + 1
    else:
        right = mid

#4. Ошибки в DFS/BFS

#❌ Забыли посещённые

# Неправильно — цикл в графе
def dfs(node):
    process(node)
    for neighbor in node.neighbors:
        dfs(neighbor)

# Правильно
def dfs(node, visited):
    if node in visited:
        return
    visited.add(node)
    ...

#❌ Неправильный backtrack

# Неправильно
path.append(node)
dfs(node)
# Забыли path.pop()!

# Правильно
path.append(node)
dfs(node)
path.pop()

#5. Ошибки в Dynamic Programming

#❌ Неправильный порядок вычислений

# Для 1D DP: слева направо
# Для 2D DP: зависит от формулы

#❌ Неправильная инициализация

# Coin Change: dp[0] = 0, остальные = inf
# Edit Distance: dp[i][0] = i, dp[0][j] = j

#❌ Изменение состояния при итерации

# Неправильно — используем обновлённые значения
for i in range(n):
    dp[i] = dp[i-1] + dp[i]  # dp[i-1] уже обновлено!

# Правильно — итерация справа налево для 1D оптимизации
for i in range(n-1, -1, -1):
    dp[i] = dp[i-1] + dp[i]

#6. Ошибки в Backtracking

#❌ Ссылка вместо копии

# Неправильно
result.append(path)  # Все элементы result ссылаются на один список!

# Правильно
result.append(path[:])  # Копия списка

#❌ Пропуск дубликатов

# После сортировки:
for i in range(start, len(nums)):
    if i > start and nums[i] == nums[i-1]:
        continue  # Пропускаем дубликаты на этом уровне

#7. Ошибки в Heap

#❌ Max-heap в Python

# Python имеет только min-heap
# Для max-heap используйте отрицание:
heapq.heappush(heap, -value)
max_val = -heapq.heappop(heap)

#❌ Изменение элементов в heap

# Неправильно — heap не обновляется
heap[0] = new_value  # Нарушает свойство кучи!

# Правильно
heapq.heapreplace(heap, new_value)

#8. Ошибки в Greedy

#❌ Слепая вера в жадность

# Greedy требует доказательства!
# Проверяйте на контрпримерах

#❌ Неправильная сортировка

# Interval Scheduling: сортировать по окончанию
intervals.sort(key=lambda x: x[1])

# Не по началу!

#9. Ошибки в Union-Find

#❌ Забыли path compression

# Неправильно — O(n) find
def find(self, x):
    if self.parent[x] != x:
        return self.find(self.parent[x])
    return self.parent[x]

# Правильно — O(α(n))
def find(self, x):
    if self.parent[x] != x:
        self.parent[x] = self.find(self.parent[x])  # Path compression
    return self.parent[x]

#10. Общие антипаттерны

#❌ Преждевременная оптимизация

# Сначала сделайте правильно, потом оптимизируйте

#❌ Игнорирование граничных случаев

# Всегда проверяйте:
# - Пустой ввод
# - Один элемент
# - Максимальный размер
# - Отрицательные числа
# - Нули

#❌ Отсутствие тестов

# Пишите тесты на:
# - Пример из условия
# - Граничные случаи
# - Минимальный ввод
# - Максимальный ввод

#11. Чеклист перед сдачей

Проверил граничные случаи (пусто, 1 элемент, максимум)
Проверил отрицательные числа и нули
Проверил сложность (время и память)
Нет ли бесконечных циклов?
Правильно ли копирую списки?
Правильно ли обновляю ответ?
Все ли базовые случаи учтены?
Нет ли выхода за границы?

#12. Заключение

Типичные ошибки:

Забыли двигать указатели
Забыли посещённые
Забыли backtrack
Ссылка вместо копии
Неправильная инициализация DP

Запоминайте и избегайте!

Common Mistakes & Anti-patterns

Разбор типичных ошибок и антипаттернов в алгоритмических задачах. Учитесь на чужих ошибках!

#1. Ошибки в Two Pointers

#❌ Бесконечный цикл

# Неправильно
while left < right:
    if condition:
        pass  # Забыли двигать указатель!

# Правильно
while left < right:
    if condition:
        left += 1
    else:
        right -= 1

#❌ Неправильное условие выхода

# Для поиска элемента: left <= right
# Для поиска пика/минимума: left < right

#2. Ошибки в Sliding Window

#❌ Забыли обновить ответ

# Неправильно
for right in range(len(s)):
    expand()
    while not valid():
        shrink()
    # Забыли: result = max(result, right - left + 1)

# Правильно
for right in range(len(s)):
    expand()
    while not valid():
        shrink()
    result = max(result, right - left + 1)

#❌ Неправильный порядок операций

# Порядок: Expand → Shrink → Update

#3. Ошибки в Binary Search

#❌ Переполнение mid

# В языках с фиксированными int:
mid = (left + right) // 2  # Может переполниться!

# Правильно:
mid = left + (right - left) // 2

#❌ Бесконечный цикл

# Неправильно
while left < right:
    mid = (left + right) // 2
    if condition(mid):
        left = mid  # Зацикливание!

# Правильно
while left < right:
    mid = left + (right - left) // 2
    if condition(mid):
        left = mid + 1
    else:
        right = mid

#4. Ошибки в DFS/BFS

#❌ Забыли посещённые

# Неправильно — цикл в графе
def dfs(node):
    process(node)
    for neighbor in node.neighbors:
        dfs(neighbor)

# Правильно
def dfs(node, visited):
    if node in visited:
        return
    visited.add(node)
    ...

#❌ Неправильный backtrack

# Неправильно
path.append(node)
dfs(node)
# Забыли path.pop()!

# Правильно
path.append(node)
dfs(node)
path.pop()

#5. Ошибки в Dynamic Programming

#❌ Неправильный порядок вычислений

# Для 1D DP: слева направо
# Для 2D DP: зависит от формулы

#❌ Неправильная инициализация

# Coin Change: dp[0] = 0, остальные = inf
# Edit Distance: dp[i][0] = i, dp[0][j] = j

#❌ Изменение состояния при итерации

# Неправильно — используем обновлённые значения
for i in range(n):
    dp[i] = dp[i-1] + dp[i]  # dp[i-1] уже обновлено!

# Правильно — итерация справа налево для 1D оптимизации
for i in range(n-1, -1, -1):
    dp[i] = dp[i-1] + dp[i]

#6. Ошибки в Backtracking

#❌ Ссылка вместо копии

# Неправильно
result.append(path)  # Все элементы result ссылаются на один список!

# Правильно
result.append(path[:])  # Копия списка

#❌ Пропуск дубликатов

# После сортировки:
for i in range(start, len(nums)):
    if i > start and nums[i] == nums[i-1]:
        continue  # Пропускаем дубликаты на этом уровне

#7. Ошибки в Heap

#❌ Max-heap в Python

# Python имеет только min-heap
# Для max-heap используйте отрицание:
heapq.heappush(heap, -value)
max_val = -heapq.heappop(heap)

#❌ Изменение элементов в heap

# Неправильно — heap не обновляется
heap[0] = new_value  # Нарушает свойство кучи!

# Правильно
heapq.heapreplace(heap, new_value)

#8. Ошибки в Greedy

#❌ Слепая вера в жадность

# Greedy требует доказательства!
# Проверяйте на контрпримерах

#❌ Неправильная сортировка

# Interval Scheduling: сортировать по окончанию
intervals.sort(key=lambda x: x[1])

# Не по началу!

#9. Ошибки в Union-Find

#❌ Забыли path compression

# Неправильно — O(n) find
def find(self, x):
    if self.parent[x] != x:
        return self.find(self.parent[x])
    return self.parent[x]

# Правильно — O(α(n))
def find(self, x):
    if self.parent[x] != x:
        self.parent[x] = self.find(self.parent[x])  # Path compression
    return self.parent[x]

#10. Общие антипаттерны

#❌ Преждевременная оптимизация

# Сначала сделайте правильно, потом оптимизируйте

#❌ Игнорирование граничных случаев

# Всегда проверяйте:
# - Пустой ввод
# - Один элемент
# - Максимальный размер
# - Отрицательные числа
# - Нули

#❌ Отсутствие тестов

# Пишите тесты на:
# - Пример из условия
# - Граничные случаи
# - Минимальный ввод
# - Максимальный ввод

#11. Чеклист перед сдачей

Проверил граничные случаи (пусто, 1 элемент, максимум)
Проверил отрицательные числа и нули
Проверил сложность (время и память)
Нет ли бесконечных циклов?
Правильно ли копирую списки?
Правильно ли обновляю ответ?
Все ли базовые случаи учтены?
Нет ли выхода за границы?

#12. Заключение

Типичные ошибки:

Забыли двигать указатели
Забыли посещённые
Забыли backtrack
Ссылка вместо копии
Неправильная инициализация DP

Запоминайте и избегайте!