Array
14. Longest Consecutive Sequence

Longest Consecutive Sequence (opens in a new tab) Medium

Problem

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

Example

Input: nums = [100, 4, 200, 1, 3, 2]

Output: 4

Summary

To solve this problem, we can use a HashSet to store all the unique elements of the input array. We can then iterate through the HashSet and for each element, if it's the first element in a consecutive sequence (i.e., its predecessor is not present in the HashSet), we can check how long the consecutive sequence is. We return the length of the longest consecutive sequence found.

Solution

In TypeScript

function longestConsecutive(nums: number[]): number {
  const numSet = new Set(nums);
  let longestStreak = 0;
 
  for (const num of numSet) {
    if (!numSet.has(num - 1)) {
      let currentNum = num;
      let currentStreak = 1;
 
      while (numSet.has(currentNum + 1)) {
        currentNum += 1;
        currentStreak += 1;
      }
 
      longestStreak = Math.max(longestStreak, currentStreak);
    }
  }
 
  return longestStreak;
}

In Python

def longestConsecutive(self, nums: List[int]) -> int:
	num_set = set(nums)
	longest_streak = 0
 
	for num in num_set:
		if num - 1 not in num_set:
			current_num = num
			current_streak = 1
 
			while current_num + 1 in num_set:
				current_num += 1
				current_streak += 1
 
			longest_streak = max(longest_streak, current_streak)
 
	return longest_streak

Step-by-step explanation

  1. Create a new Set called numSet and initialize it with the input array nums. This set will store all the unique elements from the input array.
const numSet = new Set(nums);
  1. Initialize a variable called longestStreak to store the length of the longest consecutive sequence found. Set its initial value to 0.
let longestStreak = 0;
  1. Use a for...of loop to iterate through each number num in numSet.
for (const num of numSet) {
	// ...
}
  1. Inside the loop, use an if statement to check whether the current number's predecessor (num - 1) is not in the numSet. If the predecessor is not in the set, it means num could be the first element in a consecutive sequence.
if (!numSet.has(num - 1)) {
	// ...
}
  1. If the current number is the first element in a consecutive sequence, initialize two variables:
    • currentNum: Set it to the value of num. It will be used to traverse the consecutive sequence.
    • currentStreak: Set it to 1. It represents the length of the consecutive sequence found so far, starting with the current number.
let currentNum = num;
let currentStreak = 1;
  1. Use a while loop to check whether the successor of currentNum (currentNum + 1) is present in numSet. If the successor is in the set, it means the consecutive sequence continues, and we need to update currentNum and currentStreak.
while (numSet.has(currentNum + 1)) {
	currentNum += 1;
	currentStreak += 1;
}
  1. After the while loop, we have found a consecutive sequence starting from the current number. Use Math.max to update longestStreak with the maximum value between its current value and the currentStreak.
longestStreak = Math.max(longestStreak, currentStreak);
  1. After the loop is done, return the value of longestStreak, which represents the length of the longest consecutive sequence found.
return longestStreak;

In summary, this solution uses a HashSet to store all unique elements from the input array and iterates through it. For each element that could be the first element in a consecutive sequence, it checks the length of the consecutive sequence and updates the longest consecutive sequence found accordingly. The solution returns the length of the longest consecutive sequence.

Complexity Analysis

Time Complexity

The time complexity of this solution is O(n), where n is the length of the input array. Creating a HashSet takes O(n) time, and the loop iterates through the HashSet (which has at most n elements) only once. For each iteration, the while loop checks for the consecutive sequence, which can run at most n times in total for the entire loop. Therefore, the time complexity is O(n).

Space Complexity

The space complexity of this solution is O(n), as we store all the unique elements of the input array in a HashSet. In the worst case, all elements in the input array are unique, resulting in a HashSet of size n.

13. Gas Station15. Rotate Array