Crack the Backend

Problem Statement

Given an unsorted integer array nums, return the length of the longest consecutive elements sequence (e.g. [1,2,3,4] has length 4). The sequence must be consecutive integers (no gaps). You must run in O(n) time.

Key Observations

Set + expand: Put all numbers in a Set. For each x, only start a "run" from x if x-1 is not in the set (so x is the start of a consecutive run). Then expand right: y = x, while set contains y+1, increment y. Length = y - x + 1. Update global max. Each number is touched at most twice (as start or as part of a run), so O(n).
UF alternative: Union each x with x-1 and x+1 if present; then the largest set size is the answer.

Approach

High-level: Set<Integer> set = all nums. For each num: if set does not contain num-1, then y=num, while set.contains(y+1) y++; max = Math.max(max, y-num+1). Return max.

Steps: Set<Integer> set = new HashSet<>(); for (int x : nums) set.add(x); int max = 0; for (int x : set) { if (!set.contains(x-1)) { int y = x; while (set.contains(y+1)) y++; max = Math.max(max, y-x+1); } } return max;

Implementation

Java

public int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();

    for (int x : nums) {
        set.add(x);
    }

    int max = 0;

    for (int x : set) {
        if (set.contains(x - 1)) {
            continue;
        }

        int y = x;

        while (set.contains(y + 1)) {
            y++;
        }

        max = Math.max(max, y - x + 1);
    }

    return max;
}

Test Cases

Example 1

Input

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

Expected

4

Explanation

Longest is [1,2,3,4].

Complexity Analysis

Time: O(n α(n)) ≈ O(n).
Space: O(n).

Follow-ups

Path compression + rank for optimal UF.