# Longest Consecutive Sequence
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/longest-consecutive-sequence)
Canonical: https://scaleengineer.com/dsa/problems/longest-consecutive-sequence
**Algorithms:** [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Array, Hash Table
**Companies:** [Atlassian](https://scaleengineer.com/companies/atlassian), [ByteDance](https://scaleengineer.com/companies/bytedance), [Cisco](https://scaleengineer.com/companies/cisco), [EPAM Systems](https://scaleengineer.com/companies/epam-systems), [Flipkart](https://scaleengineer.com/companies/flipkart), [Google](https://scaleengineer.com/companies/google), [IBM](https://scaleengineer.com/companies/ibm), [Infosys](https://scaleengineer.com/companies/infosys), [Oracle](https://scaleengineer.com/companies/oracle), [PayPal](https://scaleengineer.com/companies/paypal), [Paytm](https://scaleengineer.com/companies/paytm), [Roblox](https://scaleengineer.com/companies/roblox), [SAP](https://scaleengineer.com/companies/sap), [ServiceNow](https://scaleengineer.com/companies/servicenow), [TikTok](https://scaleengineer.com/companies/tiktok), [UKG](https://scaleengineer.com/companies/ukg), [Uber](https://scaleengineer.com/companies/uber), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Wissen Technology](https://scaleengineer.com/companies/wissen-technology), [Yahoo](https://scaleengineer.com/companies/yahoo), [Yandex](https://scaleengineer.com/companies/yandex), [Zoho](https://scaleengineer.com/companies/zoho), [tcs](https://scaleengineer.com/companies/tcs), [Lyft](https://scaleengineer.com/companies/lyft), [Turing](https://scaleengineer.com/companies/turing), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [Swiggy](https://scaleengineer.com/companies/swiggy), [PhonePe](https://scaleengineer.com/companies/phonepe), [Zepto](https://scaleengineer.com/companies/zepto), [DeltaX](https://scaleengineer.com/companies/deltax)
---
## 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.

**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

**Example 3:**

**Input:** nums = [1,0,1,2]
**Output:** 3

**Constraints:**

* `0 <= nums.length <= 105`
* `-109 <= nums[i] <= 109`

# Approaches
## Brute Force
This approach iterates through each number in the array. For each number, it attempts to build a sequence by repeatedly checking if the next consecutive number exists anywhere else in the array. This check is done via a linear scan.
**Time:** O(n^3) · **Space:** O(1)
**Pros:** Simple to understand and implement.; Uses constant extra space, O(1).
**Cons:** Extremely inefficient with a time complexity of O(n^3), making it impractical for even moderately sized inputs.; Will result in a 'Time Limit Exceeded' error on most coding platforms.
### Explanation
The brute-force algorithm iterates through every number in the input array `nums`. For each number `num`, it assumes it could be the start of a consecutive sequence. It then enters a `while` loop, checking for the existence of `num + 1`, `num + 2`, and so on. The check for existence is performed by another linear scan through the entire array. The length of the current sequence is tracked, and the maximum length found across all possible starting numbers is returned. This method is straightforward to conceptualize but is highly inefficient due to the nested loops and repeated scans.\n\n```java\nclass Solution {\n    private boolean arrayContains(int[] arr, int num) {\n        for (int i = 0; i < arr.length; i++) {\n            if (arr[i] == num) {\n                return true;\n            }\n        }\n        return false;\n    }\n\n    public int longestConsecutive(int[] nums) {\n        if (nums.length == 0) {\n            return 0;\n        }\n\n        int longestStreak = 0;\n\n        for (int num : nums) {\n            int currentNum = num;\n            int currentStreak = 1;\n\n            while (arrayContains(nums, currentNum + 1)) {\n                currentNum += 1;\n                currentStreak += 1;\n            }\n\n            longestStreak = Math.max(longestStreak, currentStreak);\n        }\n\n        return longestStreak;\n    }\n}\n```
### Algorithm
- Initialize a variable `maxLength` to 0.\n- For each number `num` in the input array `nums`:\n  - Initialize `currentNum = num` and `currentLength = 1`.\n  - Start a loop:\n    - Check if `currentNum + 1` exists in the `nums` array by performing a linear scan.\n    - If it exists, increment `currentLength`, update `currentNum` to `currentNum + 1`, and continue the loop.\n    - If it does not exist, break the loop.\n  - Update `maxLength = max(maxLength, currentLength)`.\n- After iterating through all numbers, return `maxLength`.

## Sorting Approach
This approach first sorts the array. After sorting, all the elements of a consecutive sequence will be grouped together, making it easy to find the longest sequence in a single linear pass over the sorted array.
**Time:** O(n log n) · **Space:** O(1) or O(log n)
**Pros:** Much more efficient than the brute-force approach.; Relatively easy to implement once the sorting idea is clear.; Space efficient, especially with in-place sorting algorithms.
**Cons:** The time complexity is dominated by sorting, which is O(n log n). This does not meet the problem's requirement of an O(n) solution.
### Explanation
The core idea is that if the numbers are sorted, we can easily find consecutive sequences by just iterating through the array once. The first step is to sort the input array `nums`. After sorting, we iterate through the array, keeping track of the current consecutive sequence length (`currentLength`) and the maximum length found so far (`maxLength`). We must handle duplicate numbers; if the current number is the same as the previous one, we simply ignore it. If the current number is one greater than the previous number, it extends the sequence, so we increment `currentLength`. If the sequence is broken (the current number is not one greater than the previous), we update `maxLength` with the `currentLength` and reset `currentLength` to 1 for the new sequence. A final check is needed after the loop to account for the longest sequence being at the end of the array.\n\n```java\nimport java.util.Arrays;\n\nclass Solution {\n    public int longestConsecutive(int[] nums) {\n        if (nums.length == 0) {\n            return 0;\n        }\n\n        Arrays.sort(nums);\n\n        int longestStreak = 1;\n        int currentStreak = 1;\n\n        for (int i = 1; i < nums.length; i++) {\n            if (nums[i] != nums[i-1]) {\n                if (nums[i] == nums[i-1] + 1) {\n                    currentStreak += 1;\n                } else {\n                    longestStreak = Math.max(longestStreak, currentStreak);\n                    currentStreak = 1;\n                }\n            }\n        }\n\n        return Math.max(longestStreak, currentStreak);\n    }\n}\n```
### Algorithm
- Handle the edge case of an empty array by returning 0.\n- Sort the input array `nums`.\n- Initialize `maxLength = 1` and `currentLength = 1`.\n- Iterate through the sorted array from the second element (`i = 1`).\n- If `nums[i]` is not equal to `nums[i-1]` (i.e., not a duplicate):\n  - Check if `nums[i]` is equal to `nums[i-1] + 1`.\n  - If it is, increment `currentLength`.\n  - If it's not, the sequence is broken. Update `maxLength = max(maxLength, currentLength)` and reset `currentLength = 1`.\n- After the loop finishes, update `maxLength` one last time: `maxLength = max(maxLength, currentLength)`.\n- Return `maxLength`.

## Optimal Approach using Hash Set
This approach achieves linear time complexity by using a Hash Set for fast O(1) lookups. It intelligently avoids redundant work by only building sequences from their starting numbers (i.e., a number `x` where `x-1` is not present).
**Time:** O(n) · **Space:** O(n)
**Pros:** Achieves the optimal O(n) time complexity, satisfying the problem's constraints.; The logic is elegant, avoiding redundant computations by only checking sequences from their starting points.
**Cons:** Requires extra space of O(n) for the hash set, whereas the sorting approach can be done in-place.
### Explanation
This method provides an optimal solution with O(n) time complexity as required by the problem. First, all numbers from the input array are inserted into a `HashSet`. This allows for checking the presence of a number in average O(1) time. Then, the algorithm iterates through the numbers. For each number `num`, it performs a crucial check: if `num - 1` also exists in the set. If it does, it means `num` is part of a sequence we have already counted or will count starting from a smaller number, so we skip it. This check is the key to achieving O(n) time complexity, as it ensures we only start building a sequence from its absolute smallest element. If `num - 1` is not in the set, we start counting a new sequence. We use a `while` loop to check for `num + 1`, `num + 2`, etc., in the set, incrementing a counter. The maximum length is updated after each full sequence is counted. Although there is a nested loop, each number is visited at most twice, leading to a linear time complexity overall.\n\n```java\nimport java.util.HashSet;\nimport java.util.Set;\n\nclass Solution {\n    public int longestConsecutive(int[] nums) {\n        if (nums == null || nums.length == 0) {\n            return 0;\n        }\n\n        Set<Integer> numSet = new HashSet<>();\n        for (int num : nums) {\n            numSet.add(num);\n        }\n\n        int longestStreak = 0;\n\n        for (int num : numSet) {\n            // Only start counting if 'num' is the beginning of a sequence\n            if (!numSet.contains(num - 1)) {\n                int currentNum = num;\n                int currentStreak = 1;\n\n                while (numSet.contains(currentNum + 1)) {\n                    currentNum += 1;\n                    currentStreak += 1;\n                }\n\n                longestStreak = Math.max(longestStreak, currentStreak);\n            }\n        }\n\n        return longestStreak;\n    }\n}\n```
### Algorithm
- If the input array is empty, return 0.\n- Create a `HashSet` and add all elements of `nums` to it.\n- Initialize `maxLength = 0`.\n- Iterate through each `num` in the set.\n- Check if `set.contains(num - 1)`. If it does, `num` is not the start of a sequence, so continue to the next number.\n- If `num - 1` is not in the set, we have found the start of a sequence.\n- Initialize `currentNum = num` and `currentLength = 1`.\n- While `set.contains(currentNum + 1)`:\n  - Increment `currentLength` and update `currentNum` to `currentNum + 1`.\n- After the while loop, update `maxLength = max(maxLength, currentLength)`.\n- After iterating through all numbers, return `maxLength`.

# Solutions
### Java

```java
class Solution { public int longestConsecutive ( int [] nums ) { Set < Integer > s = new HashSet <>(); for ( int x : nums ) { s . add ( x ); } int ans = 0 ; for ( int x : nums ) { if (! s . contains ( x - 1 )) { int y = x + 1 ; while ( s . contains ( y )) { ++ y ; } ans = Math . max ( ans , y - x ); } } return ans ; } }
```

### JavaScript

```javascript
/** * @param {number[]} nums * @return {number} */ var longestConsecutive =
  function (nums) {
    const s = new Set(nums);
    let ans = 0;
    for (const x of nums) {
      if (!s.has(x - 1)) {
        let y = x + 1;
        while (s.has(y)) {
          y++;
        }
        ans = Math.max(ans, y - x);
      }
    }
    return ans;
  };

```

### CPP

```cpp
class Solution { public: int longestConsecutive ( vector < int >& nums ) { unordered_set < int > s ( nums . begin (), nums . end ()); int ans = 0 ; for ( int x : nums ) { if ( ! s . count ( x - 1 )) { int y = x + 1 ; while ( s . count ( y )) { y ++ ; } ans = max ( ans , y - x ); } } return ans ; } };
```

### Python

```python
class Solution : def longestConsecutive ( self , nums : List [ int ]) -> int : s = set ( nums ) ans = 0 for x in nums : if x - 1 not in s : y = x + 1 while y in s : y += 1 ans = max ( ans , y - x ) return ans
```