Longest Consecutive Sequence | Array & Hashing | Neetcode 150

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.

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

Before we solve this question, let's understand where is this kind of pattern useful?

User Story:

You are a backend engineer at Amazon AWS working on S3 Storage logs. S3 buckets generate logs of access timestamps when customers retrieve or modify files. Logs arrive out of order because of:

• Distributed systems where logs are generated across different servers.
• Network delays causing some logs to arrive late.

Your team is tasked to identify consecutive periods of activity in the logs to:

• Generate usage analytics: Find the longest sequence of active hours for customers.
• Detect anomalies: Identify gaps (inactive hours) where activity is unexpectedly missing.

Technical Requirements:

• Efficiency: Solve the problem in O(n) time.
• Scalability: Handle hundreds of millions of logs without running out of memory.
• Real-time Analytics: The system needs to process logs and output results quickly

Why Is This Useful in FAANG?

1. Handling Unordered Data:

• Logs in real-world systems (AWS, GCP, Meta) arrive unordered due to distributed nature.
• Efficiently processing such unordered timestamps is a common challenge.

1. Real-Time Systems:

• Sorting logs (O(n log n)) is too slow for real-time analytics.
• HashSet provides O(1) lookups for optimal performance.

1. Scalability:

• Hashing allows us to handle massive datasets (billions of logs daily) without performance degradation.

1. Anomaly Detection:

• Gaps in consecutive timestamps can highlight anomalies like unexpected downtime or system delays.

Business Impact:

For Amazon:

• Detecting the longest active periods helps customers optimize their bucket usage.
• Identifying gaps in logs helps the team debug and improve system reliability.

For Facebook/Meta:

• Similar logic applies to user activity analytics:
• Find the longest consecutive period users were active on a platform.
• Identify drops or gaps in engagement.

For Google:

• This can be applied to search query logs:
• Detect long, continuous hours of search activity.
• Identify and report unusual query downtimes.

What can be derived from this question:

1. No nested loop of nums size to abide by O(N)
2. We cannot sort our array num
3. Consecutive sequence = x -2 , x -1, x , x +1 , x+2
4. Can we iterate through our array and use hash to store all our items?
5. Later we will again run another loop and check if @ i, nums[i -1], or nums[i+1] exist

Let's work on the solution:

[100,4,200,1,3,2]
@ 100, we check for 100 -1 = 99, does it exist in the map?
as we are looking for the start of a sequence

since we don't have 99, we assume 100, itself must be the start of the sequnce.

if 100 is the start of the sequence, then we look for 101 by doing nums[i]= 100 + 1
and if we find 101, the we say our length ++
if not, then we will move to 4
and do the same thing. 

A framework of how a longest consecutive sequence can be retrieved.

var longestConsecutive = function(nums) {

const myMap = new Map()

for(let i = 0; i <nums.length;i++){
  myMap.set(nums[i], true)
}

for(let i = 0; i < nums.length; i++){
 if(!myMap.has(nums[i] -1)){
   // if there is no x-1, x must be the start of the sequence
   
   let count = 0
   let x = nums[i]

   // no we check for x + 1, x + 2 , x + n and so on

   while(myMap.has(x + 1)){
    // if for 100, 101 is found or for x , x + 1 is found,
    // we look for 102, or x + 2
    count ++
    x++
   } 
 
   // check if current consecutive is larger than previously
   max = Math.max(max, count) 
 }
}
return max

}