Arrays and Hashing

Problem: longest run of consecutive values

You get an unsorted array of integers. Find the length of the longest set of values that form a run of consecutive integers, such as 1, 2, 3, 4. The values can appear anywhere in the array and in any order. For [100, 4, 200, 1, 3, 2] the answer is 4 (the run 1–4).

Brute force

Sort the array, then walk it, counting how long each run of +1 steps lasts (skip duplicates). That is O(n log n). Interviewers usually follow up with "can you do it in O(n)?"

Key insight

Put every value in a HashSet. A value x starts a run only if x - 1 is not in the set. Count forward only from those starting points. Each value is then visited by at most one forward walk, so the total work is linear.

Optimal solution

Set<Integer> set = new HashSet<>();
for (int x : a) set.add(x);
int best = 0;
for (int x : set) {
    if (set.contains(x - 1)) continue;   // not the start of a run
    int y = x;
    while (set.contains(y + 1)) y++;
    best = Math.max(best, y - x + 1);
}

Loop over the set, not the array. With many duplicates, looping over the array would repeat the same walk again and again.

Complexity

• Time: O(n) on average. The inner while runs at most n times in total across the whole loop, not n times per value.
• Space: O(n) for the set.

In interviews: say why the nested loop is still linear. That explanation is what the interviewer is waiting for.