LeetCode 128. Longest Consecutive Sequence

The Problem

Link to original problem on LeetCode.

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.

Examples

Example 1:

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.

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9
Constraints
  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109

My Solution

An efficient way to solve this problem without iterating over the array nums any more times than necessary is to use a depth first search. We will create a Map of each digit in nums, and use that Map to keep track of whether we've evaluated a given digit or not as part of a consecutive sequence. Inside our depth first search, we'll increment a result every time we find a consecutive digit in the nums array, as well as add the result of depth first search of that consecutive digit. We'll iterate over each number in nums and set a final result variable equal to the maximum of itself or the result of a depth first search of itself. This will ultimately give us the longest consecutive sequence.

function longestConsecutive(nums: number[]): number {
// Return early if there are no numbers
if (nums.length === 0) return 0;

// First, we create a Map for each number in nums.
// The number will be the key, and the value false.
// False implies "no, we haven't checked this node".
const map: Map<number, boolean> = new Map();
nums.forEach(num => map.set(num, 0));

// Here we define our depth first search function.
function dfs(digit: number) {
let result = 0;
// First, check if the next highest number exists
// in the map and if it hasn't been traversed yet.
// If so, mark it traversed and increment the result
// by 1 plus the eventual result of all possible
// next consecutive digits.
if (map.has(digit + 1) && map.get(digit + 1) === false) {
map.set(digit + 1, true);
result += 1 + dfs(digit + 1);
}
// Same as above, but going the other way.
if (map.has(digit - 1) && map.get(digit - 1) === false) {
map.set(digit - 1, true);
result += 1 + dfs(digit - 1);
}

// By now, result equals the full length of all
// consecutive numbers in the chain where the digit
// is a member of that chain. All numbers in that
// chain are marked as visited, so we won't need
// to check them again later.
return result;
}

// Initialize our result to 1, since we already
// bailed if there are no numbers in nums.
let result = 1;

// For each number in nums, set the result to the
// maximum of itself or the result of our depth
// first search for that number.
nums.forEach(num => {
if (map.get(num) === false) {
result = Math.max(result, dfs(num));
}
})

// Finally, return our result!
return result;
};

This solution has to traverse the array nums twice: once to create the Map, and once to run the dfs function on each number. This gives us time complexity of O(2n)O(2n), which reduces to just O(n)O(n). Space complexity due to our Map is O(n)O(n).