Find longest consecutive subsequence

The problem, simply

You get an unsorted array of whole numbers. Find the longest set of values that make a run of numbers that follow each other, like 5, 6, 7, 8. The values can be anywhere in the array, in any order. Give back the length of that run.

Repeated values count once. An empty array has answer 0.

A story to remember it

Picture it

Examples

Way 1: the simple way

Sort the array. Now runs sit next to each other. Walk along and count how long each run is.

1. Sort.
2. For each i > 0: if arr[i] equals arr[i-1], it is a repeat, skip it. If arr[i] == arr[i-1] + 1, the run grows. Otherwise a new run starts at length 1.
3. Keep the longest run.

class Solution {
    public int longestConsecutive(int[] arr) {
        if (arr.length == 0) return 0;
        int[] a = arr;
        Arrays.sort(a);                               // sorts the input in place
        int best = 1, run = 1;
        for (int i = 1; i < a.length; i++) {
            if (a[i] == a[i - 1]) continue;           // a repeat does not change the run
            if (a[i] == a[i - 1] + 1) run++;          // the run keeps going
            else run = 1;                             // a gap: a new run starts
            best = Math.max(best, run);
        }
        return best;
    }
}

How long it takes: sorting costs O(n log n), the walk O(n). Extra room: O(1) besides the sort itself, because we sort in place. Copy the array first if the caller needs it unchanged. The very first idea, "for each number, search the whole array for the next number", is much slower at O(n^3).

Way 2: the clever way

Put every number in a bag where "is x here?" takes one step (a hash set). Then only count up from numbers that start a run.

1. Add all numbers to the set.
2. For each number x in the set: if x - 1 is also in the set, skip x. It is in the middle of a run.
3. Otherwise x starts a run. Count x + 1, x + 2, ... while they are in the set.
4. Keep the longest count.

The skip in step 2 is what makes it fast. Without it, every number in a run of length L would count the rest of the run again, and that costs O(n^2).

class Solution {
    public int longestConsecutive(int[] arr) {
        Set<Integer> bag = new HashSet<>();
        for (int x : arr) bag.add(x);
        int best = 0;
        for (int x : bag) {                         // walk the set, so repeats are seen once
            if (bag.contains(x - 1)) continue;      // not the front of a run
            int run = 1;
            while (bag.contains(x + run)) run++;    // count up from the front
            best = Math.max(best, run);
        }
        return best;
    }
}

How long it takes: each number is checked once as a possible start, and each number is counted inside at most one run, so about 2n lookups, O(n) on average. Extra room: the set, O(n).

Watch out for

• Loop over the set, not the array. With many copies of the front number, looping over the array repeats the same count again and again.
• x + 1 overflows when x is Integer.MAX_VALUE. It wraps to the smallest int, which is only a problem if that value is also in the array. Use long math to be fully safe.
• Repeats must not grow the run. The sort version needs the a[i] == a[i-1] skip for this.

What interviewers ask next

• Return the run itself? Remember the front x and the length of the best run, then output x, x+1, ....
• Can union find solve it? Yes. Join x with x + 1 whenever both exist, and track the size of each group. The biggest group is the answer, in nearly O(n).
• What if numbers arrive one at a time and you must answer after each? Keep a map from each run's ends to its length. A new x joins the run ending at x - 1 and the run starting at x + 1, updating only the two outer ends.
• Why not sort? Sorting is O(n log n). Interviewers asking this question usually want the O(n) set idea.

Remember this

Grown-up words: the bag is a hash set with O(1) average lookups, a run is a consecutive sequence, and the "front of the line" check is what makes the total work linear (amortized O(n)).