Longest Consecutive Sequence

🔗 Problem Link: https://leetcode.com/problems/longest-consecutive-sequence/

The Longest Consecutive Sequence problem asks us to find the length of the longest sequence of consecutive integers in an unsorted array.

While the brute force solution repeatedly searches for the next consecutive number, the optimal solution uses hashing to identify sequence starting points and build sequences efficiently.

---

Brute Force Approach

Intuition

For every number, keep checking whether the next consecutive number exists in the array.

If it exists, continue extending the sequence. Otherwise, stop and update the maximum length found so far.

Since searching for a number requires scanning the entire array, this becomes inefficient for large inputs.

Time & Space Complexity

• Time Complexity: O(N²)
• Space Complexity: O(1)

Java Solution

```java id="0mpj18"
class Solution {

public int longestConsecutive(int[] nums) {

    int longest = 0;

    for(int num : nums) {

        int current = num;
        int length = 1;

        while(contains(nums, current + 1)) {
            current++;
            length++;
        }

        longest = Math.max(longest, length);
    }

    return longest;
}

private boolean contains(int[] nums, int target) {

    for(int num : nums) {
        if(num == target) {
            return true;
        }
    }

    return false;
}

}

---

## Optimizing the Solution

The key observation is:

A number can only be the start of a sequence if its previous number does not exist.

For example:



```text id="av9f5t"
[100,4,200,1,3,2]

Here:

• 1 is a valid starting point.
• 2 is not because 1 exists.
• 3 is not because 2 exists.
• 4 is not because 3 exists.

Instead of starting a sequence from every element, we only start from valid sequence beginnings.

This avoids redundant work and gives us a linear-time solution.

---

Optimal Approach (HashMap)

Time & Space Complexity

• Time Complexity: O(N)
• Space Complexity: O(N)

Java Solution

```java id="mr0t5l"
class Solution {

public int longestConsecutive(int[] nums) {

    HashMap<Integer, Boolean> map = new HashMap<>();

    for(int num : nums) {
        map.put(num, true);
    }

    for(int num : nums) {

        if(map.containsKey(num - 1)) {
            map.put(num, false);
        }
    }

    int maxLength = 0;

    for(int num : nums) {

        if(map.get(num)) {

            int length = 1;

            while(map.containsKey(num + length)) {
                length++;
            }

            maxLength = Math.max(maxLength, length);
        }
    }

    return maxLength;
}

}

---

## Dry Run

### Input



```text id="h6vk5r"
nums = [100,4,200,1,3,2]

Step 1: Mark Every Number as a Potential Starting Point

```text id="rm3f7s"
100 -> true
4 -> true
200 -> true
1 -> true
3 -> true
2 -> true

### Step 2: Remove Numbers Having a Predecessor

If `(num - 1)` exists, it cannot be the beginning of a sequence.



```text id="sl2w9v"
4 -> false (3 exists)
3 -> false (2 exists)
2 -> false (1 exists)

Remaining starting points:

```text id="4xgn3w"
100
200
1

### Step 3: Build Consecutive Sequences



```text id="i6qtx8"
100 -> length = 1

200 -> length = 1

1 -> 2 -> 3 -> 4
length = 4

Answer

```text id="qvj2y1"
4

---

## Key Interview Takeaway

The trick is not finding consecutive numbers.

The trick is identifying only the valid sequence starting points and building sequences from there.

This simple observation reduces the solution from **O(N²)** to **O(N)** and is exactly what interviewers look for.

---

Follow along as I break down the intuition, brute force, better, and optimal solutions for every problem.

**Master the starting-point pattern once, and many hashing problems become much easier to solve.**