Longest Consecutive Sequence

The Problem Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence. You must write an algorithm that runs in O(n) time. A consecutive sequence is a sequence of elements in which each element is exactly 1 greater than the previous element. Examples Input: nums = [100, 4, 200, 1, 3, 2] Output: 4 Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4. Input: nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1] Output: 9 Constraints 0 <= nums.length <= 10^5 -10^9 <= nums[i] <= 10^9 Brute Force Solution func longestConsecutive(_ nums: [Int]) -> Int { var res = 0 let setOfNums: Set<Int> = Set(nums) for num in nums { var streak = 0 var curr = num while setOfNums.contains(curr) { streak += 1 curr += 1 } res = max(res, streak) } return res } Explanation Let’s start with the brute force solution. We need to increment each element by 1 to check if the incremented value exists in our input array. For example, if we have an array nums with [3, 2, 1, 100, 5], the longest consecutive sequence will be 3. If you look closely at the array [3, 2, 1, 100, 5], it has a sequence of 2, 1, which when incremented forms elements that already exist in the array (1 -> 2, 2 -> 3). By counting the number of increments, you can determine the longest sequence. The solution above does exactly that: ...