Longest Consecutive Sequence

Решение

Подход

Эта задача кажется очень похожей на сортировку (O(n log n)), но есть оптимальное O(n) решение, использующее HashSet.

Ключевая идея: вместо проверки всех чисел, мы начинаем считать последовательность только с тех чисел, которые являются началом последовательности (т.е. n-1 не существует в множестве).

Оптимальное решение O(n) время, O(n) память

func longestConsecutive(_ nums: [Int]) -> Int {
    guard !nums.isEmpty else { return 0 }
    
    // Создаём Set для O(1) поиска
    let numSet = Set(nums)
    var maxLength = 0
    
    for num in numSet {
        // Начинаем считать только если это начало последовательности
        // (т.е. num-1 не в множестве)
        if !numSet.contains(num - 1) {
            var currentNum = num
            var currentLength = 1
            
            // Считаем длину последовательности
            while numSet.contains(currentNum + 1) {
                currentNum += 1
                currentLength += 1
            }
            
            maxLength = max(maxLength, currentLength)
        }
    }
    
    return maxLength
}

Почему это O(n)?

Хотя это выглядит как вложенный цикл, каждое число обрабатывается максимум два раза:

1. Один раз в основном цикле for num in numSet
2. Один раз в while цикле как currentNum

Общее количество итераций = O(n) + O(n) = O(n)

Пошаговый разбор примера

Вход: [100, 4, 200, 1, 3, 2]

Шаг 1: numSet = {100, 4, 200, 1, 3, 2}

Шаг 2: Итерация по numSet (порядок не определен в Set, но важна логика):

  num = 100:
    100-1=99 не в numSet → начало последовательности
    Считаем: 100, 101? нет
    Длина: 1

  num = 4:
    4-1=3 в numSet → не начало, пропускаем

  num = 200:
    200-1=199 не в numSet → начало
    Считаем: 200, 201? нет
    Длина: 1

  num = 1:
    1-1=0 не в numSet → начало
    Считаем: 1, 2? да → 2, 3? да → 3, 4? да → 4, 5? нет
    Длина: 4 ✓

  num = 3:
    3-1=2 в numSet → не начало, пропускаем

  num = 2:
    2-1=1 в numSet → не начало, пропускаем

Максимальная длина: 4

Наивное решение O(n log n) — НЕ оптимально

func longestConsecutiveNaive(_ nums: [Int]) -> Int {
    guard !nums.isEmpty else { return 0 }
    
    let sorted = nums.sorted()  // O(n log n)
    var maxLength = 1
    var currentLength = 1
    
    for i in 1..<sorted.count {
        if sorted[i] == sorted[i-1] + 1 {
            currentLength += 1
        } else if sorted[i] != sorted[i-1] {
            maxLength = max(maxLength, currentLength)
            currentLength = 1
        }
        // Если sorted[i] == sorted[i-1], это дубликат, пропускаем
    }
    
    return max(maxLength, currentLength)
}

Это работает, но медленнее из-за сортировки.

Обработка дубликатов

func longestConsecutiveWithDuplicates(_ nums: [Int]) -> Int {
    guard !nums.isEmpty else { return 0 }
    
    let numSet = Set(nums)  // Автоматически удаляет дубликаты
    var maxLength = 0
    
    for num in numSet {
        if !numSet.contains(num - 1) {
            var currentNum = num
            var currentLength = 1
            
            while numSet.contains(currentNum + 1) {
                currentNum += 1
                currentLength += 1
            }
            
            maxLength = max(maxLength, currentLength)
        }
    }
    
    return maxLength
}

// Использование Set уже обработал дубликаты
print(longestConsecutiveWithDuplicates([0, 3, 7, 2, 5, 8, 4, 6, 0, 1]))
// Output: 9 (последовательность 0-8, второй 0 игнорируется)

Тестирование

// Пример 1
print(longestConsecutive([100, 4, 200, 1, 3, 2]))  // 4

// Пример 2
print(longestConsecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1]))  // 9

// Граничные случаи
print(longestConsecutive([]))  // 0
print(longestConsecutive([1]))  // 1
print(longestConsecutive([1, 1, 1]))  // 1 (дубликаты)
print(longestConsecutive([9, 1,4, 7, 3, 2, 8, 5, 6]))  // 9 (все подряд)
print(longestConsecutive([0]))  // 1
print(longestConsecutive([-1, 0, 1]))  // 3 (с отрицательными)
print(longestConsecutive([1000000000, -1000000000]))  // 1 (огромный диапазон)

// Пример с повтором в начале
print(longestConsecutive([0, 0, 0, 1, 2, 3]))  // 4

// Пример с разрывом в последовательности
print(longestConsecutive([1, 2, 0, 1]))  // 3

Визуализация алгоритма

Массив: [100, 4, 200, 1, 3, 2]
         ↓    ↓   ↓    ↓  ↓  ↓
Set:    {100, 4, 200,  1, 3, 2}

Проверяем каждый элемент:

100 → нет 99? ✓ Начало!
      есть 101? ✗
      Длина: 1

4 → нет 3? ✗ Не начало, пропускаем

200 → нет 199? ✓ Начало!
      есть 201? ✗
      Длина: 1

1 → нет 0? ✓ Начало!
    есть 2? ✓ → 3? ✓ → 4? ✓ → 5? ✗
    Длина: 4 ← МАКСИМУМ

3 → нет 2? ✗ Не начало, пропускаем

2 → нет 1? ✗ Не начало, пропускаем

Результат: 4

Анализ сложности

Вариации на собеседовании

Вопрос: Что если нужна сама последовательность, а не только длина? Ответ:

func longestConsecutiveSequence(_ nums: [Int]) -> [Int] {
    guard !nums.isEmpty else { return [] }
    
    let numSet = Set(nums)
    var maxSequence: [Int] = []
    
    for num in numSet {
        if !numSet.contains(num - 1) {
            var currentNum = num
            var currentSequence = [currentNum]
            
            while numSet.contains(currentNum + 1) {
                currentNum += 1
                currentSequence.append(currentNum)
            }
            
            if currentSequence.count > maxSequence.count {
                maxSequence = currentSequence
            }
        }
    }
    
    return maxSequence
}

print(longestConsecutiveSequence([100, 4, 200, 1, 3, 2]))
// Output: [1, 2, 3, 4]

Вопрос: Что если ограничения памяти очень строгие? Ответ: Используйте отсортированный подход O(n log n) с O(1) памятью.

Рекомендация для интервью

Начните с объяснения:

1. "Я вижу, что сортировка даст O(n log n)"
2. "Но есть трюк с Set — мы можем сделать O(n)"
3. "Ключевой момент: начинаем считать только с начала последовательности"
4. "Это гарантирует, что каждое число обработано максимум дважды"

Затем напишите код и протестируйте на примерах.