A returns warehouse dumps occupied bin IDs in whatever order the scanners finished. Ops wants the longest stretch of consecutive occupied bins for one outbound wave. The first version, for each ID, asked “is ID+1 in the dump?” and walked until a gap. A few thousand bins returned instantly; a million-row holiday dump was still asking when the wave planner timed out.

Longest Consecutive Sequence asks for the longest run of consecutive values. An array already gives a[i] for free. Nested “is x+1 present?” uses that and still pays a restarted scan. Sorting unique values makes the neighbor walk linear after the sort, which is O(n log n), not the bar they named.

This is an interview writeup, not a hashing lecture. The hash table post owns buckets and collisions. Here we only care about membership: is x in the set, and is x - 1 missing?

The problem

Given an int[] nums, return the length of the longest run of consecutive integers that appear as values. [1, 3, 2] is a run of length 3 even though the array is scrambled. Duplicates do not lengthen a run, an empty array is length 0, and expected linear time is the bar.

nums = [100, 4, 200, 1, 3, 2]   →  4    because 1, 2, 3, 4
nums = [20, 7, 5, 6, 4, 20]     →  4    because 4, 5, 6, 7
nums = []                       →  0

Note: Consecutive means k, k+1, k+2, … as values, not as adjacent slots. Index order is a red herring.

Nested “is next present” is the honest brute force

From every x, walk x+1, x+2, … while each successor sits somewhere in the array. Correct. Each walk restarts a linear scan, so already-consecutive 1..n is cubic in the array and still quadratic in a set if you start from every x.

int longestConsecutiveNested(int[] nums) {
    int best = 0;
    for (int x : nums) {
        int y = x;
        int len = 1;
        while (containsValue(nums, y + 1)) {
            y++;
            len++;
        }
        if (len > best) {
            best = len;
        }
    }
    return best;
}

boolean containsValue(int[] nums, int target) {
    for (int n : nums) {
        if (n == target) {
            return true;
        }
    }
    return false;
}

Sort unique values, then scan adjacent numbers. That is the other honest brute: O(n log n) time, correct, and still the wrong bill when they said expected O(n).

Start a run only at the left edge

Put every value in a HashSet. A number x is the left edge of a run only when x - 1 is not a member. Grow x, x+1, x+2, … from those edges only — every streak is counted once, interiors skipped.

nums = [100, 4, 200, 1, 3, 2]
set  = {100, 4, 200, 1, 3, 2}

x=100   99 missing    walk 100            length 1
x=4     3 present     skip (not a left edge)
x=200   199 missing   walk 200            length 1
x=1     0 missing     walk 1, 2, 3, 4     length 4
x=3     2 present     skip
x=2     1 present     skip

best = 4

Set iteration order does not matter. Each unique value is considered once. The Java is that walk:

int longestConsecutive(int[] nums) {
    Set<Integer> values = new HashSet<>();
    for (int n : nums) {
        values.add(n);
    }
    int best = 0;
    for (int x : values) {
        if (values.contains(x - 1)) {
            continue;
        }
        int y = x;
        int len = 1;
        while (values.contains(y + 1)) {
            y++;
            len++;
        }
        if (len > best) {
            best = len;
        }
    }
    return best;
}

Time is expected O(n) — one pass to fill the set, then each unique value is a left-edge test; each value is visited as a successor at most once. Space is O(n) for the set. Worst-case hash degeneration is the same story the hash-table post already told; do not re-lecture it at the whiteboard unless they ask.

Note: If you grow a run from every x, you recount the same streak. From 1 you walk 1,2,3,4; from 2 you walk 2,3,4 again. The left-edge skip is what keeps the inner walk linear, not the set by itself.

What interviewers usually poke next

  • Duplicates. The set collapses repeats. [1, 1, 2, 2] is still length 2. Do not add 1 for a duplicate; consecutive is about distinct values in a numeric run.
  • Empty array. The set stays empty, the loop never runs, return 0. Do not invent a special case unless they ask.
  • They relax the bound. Sort unique, then scan neighbors. That is O(n log n), correct, and accepted if they drop expected linear. Say the bound out loud before you sort: if they still want O(n), the set-and-left-edge walk is the answer.

You are done with this problem when you can say, out loud, why nested “is next present” is correct, why sorting unique is legal but not linear, and why you start a run only when x - 1 is missing.