128. Longest Consecutive Sequence

INFO

Problem: Longest Consecutive Sequence

Pattern: Set lookup / sequence start detection

This problem asks for the length of the longest run of consecutive integers in an unsorted array. Sorting would make the problem easier, but it would cost O(n log n). The expected approach uses a set so membership checks are fast.

The key idea is to only start counting from numbers that are the beginning of a sequence. A number is a sequence start when num - 1 does not exist in the set.

Approach

1. Insert all numbers into a Set<Int>.
2. Loop through each unique number in the set.
3. If num - 1 exists, skip it because this number is not the start.
4. If num - 1 does not exist, count upward: num + 1, num + 2, and so on.
5. Track the largest count found.

This avoids repeatedly recounting the same sequence. For example, in [1, 2, 3, 4], only 1 starts the sequence. The numbers 2, 3, and 4 are skipped as starting points.

Swift Notes

Swift sets provide fast contains checks and automatically remove duplicate values. That matters because duplicates should not extend a consecutive sequence.

The implementation stores the input in numsSet, then checks for sequence starts before walking forward with currentNumber.

Complexity

• Time complexity: O(n) on average because each number is visited a limited number of times.
• Space complexity: O(n) for the set.

Edge Cases

• An empty array should return 0.
• Duplicates should not inflate the sequence length.
• Negative numbers work normally because set lookup is value-based.

class Solution {
    func longestConsecutive(_ nums: [Int]) -> Int {
        let numsSet = Set(nums)
        var currentNumber = 0
        var longestSequence = 0
        for num in numsSet {
            if !numsSet.contains(num - 1) {
                var newLength = 1
                currentNumber = num + 1
                while numsSet.contains(currentNumber) {
                    newLength += 1
                    currentNumber += 1
                }
                longestSequence = max(longestSequence, newLength)
            }
        }
        return longestSequence
    }
}

let solution = Solution()

let testcase1 = solution.longestConsecutive([100,4,200,1,3,2])
print(testcase1) // 4

let testcase2 = solution.longestConsecutive([0,3,7,2,5,8,4,6,0,1])
print(testcase2) // 9