Longest Consecutive Sequence

Medium Arrays & Hashing Hash Set Lookup Original on LeetCode

Longest Consecutive Sequence is a medium arrays & hashing problem solved with the hash set lookup pattern. The best approach, optimal (hash set, count only from run starts), runs in O(n) time and O(n) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (extend each value by searching) up.

Problem

Given an unsorted integer array nums, return the length of the longest run of consecutive integers whose values all appear in nums. A run is a set of values like x, x + 1, x + 2, …; the values may appear anywhere in the array, in any order.

Repeated values count once. Try to solve it in O(n) time.

Examples

Example 1

Input
nums = [10, 4, 20, 3, 11, 5, 2]
Output
4
Why
The values 2, 3, 4, 5 form a run of four consecutive integers; 10, 11 is only a run of two.

Example 2

Input
nums = [7, -1, 0, 7, 1, -2, 8]
Output
4
Why
-2, -1, 0, 1 is the longest run. The repeated 7 does not lengthen 7, 8.

Example 3

Input
nums = []
Output
0
Why
No values, no run.

Constraints

  • 0 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • Aim for O(n) time.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (extend each value by searching)O(n³)O(1)
Better (sort, then count runs)O(n log n)O(n)
Optimal (hash set, count only from run starts)O(n)O(n)

1Brute force (extend each value by searching)

TimeO(n³)Each of the n starts can extend up to n times, and each extension scans the n elements.
SpaceO(1)Only counters.

Treat every value as a possible start and keep looking for the next integer by scanning the whole array, counting how far the run goes.

  1. For each x in nums: cur = x, len = 1.
  2. While the array contains cur + 1 (checked with a linear scan), increment cur and len.
  3. Keep the largest len.
class Solution {
    public int longestConsecutive(int[] nums) {
        int best = 0;
        for (int x : nums) {
            int cur = x, len = 1;
            while (contains(nums, cur + 1)) {
                cur++;
                len++;
            }
            best = Math.max(best, len);
        }
        return best;
    }

    private boolean contains(int[] nums, int v) {
        for (int x : nums) if (x == v) return true;
        return false;
    }
}

2Better (sort, then count runs)

TimeO(n log n)Sorting dominates; the walk is O(n).
SpaceO(n)The sorted copy.

Sort a copy of the array so consecutive integers sit next to each other. Walk it once: equal neighbors are skipped, a neighbor that is exactly one larger extends the run, and anything else starts a new run.

  1. Sort the values.
  2. For i from 1: if a[i] == a[i - 1], skip; if a[i] == a[i - 1] + 1, run++; otherwise run = 1.
  3. Track the largest run (0 for an empty array).
class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) return 0;
        int[] a = nums.clone();
        Arrays.sort(a);
        int best = 1, run = 1;
        for (int i = 1; i < a.length; i++) {
            if (a[i] == a[i - 1]) continue;
            if (a[i] == a[i - 1] + 1) run++;
            else run = 1;
            best = Math.max(best, run);
        }
        return best;
    }
}

3Optimal (hash set, count only from run starts)

TimeO(n)Each value is inserted once, checked once as a possible start, and stepped over by at most one run walk.
SpaceO(n)The hash set holds up to n values.

Put every value in a hash set. A value v starts a run exactly when v - 1 is not in the set. From each start, count upward while v + 1, v + 2, … are present. Every value is visited by at most one such walk, so the total work is linear.

  1. Add all values to a set.
  2. For each v in the set: if v - 1 is in the set, skip it (it is not a start).
  3. Otherwise count len while v + len is in the set, and keep the largest len.
class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int x : nums) set.add(x);
        int best = 0;
        for (int v : set) {
            if (set.contains(v - 1)) continue;
            int len = 1;
            while (set.contains(v + len)) len++;
            best = Math.max(best, len);
        }
        return best;
    }
}

Edge cases to test

  • Empty array
  • Duplicates inside a run, which must be counted once
  • Negative numbers and runs that cross zero
  • All values equal: the answer is 1
  • Values far apart, so every run has length 1

Hints

Hint 1

Order in the array does not matter; only which values are present. Sorting puts runs next to each other, but costs O(n log n).

Hint 2

Put every value in a hash set so you can ask 'is v + 1 present?' in O(1).

Hint 3

Only start counting from a value v whose v - 1 is NOT in the set. Then each run is walked exactly once.

FAQ

What is the best time complexity for Longest Consecutive Sequence?

Optimal (hash set, count only from run starts) runs in O(n) time and O(n) extra space. Each value is inserted once, checked once as a possible start, and stepped over by at most one run walk.

Which pattern does Longest Consecutive Sequence use?

It is a arrays & hashing problem that uses the hash set lookup pattern. Other problems with the same pattern: Contains Duplicate, Fair Candy Swap, Maximize Area of Square Hole in Grid.

Is there a brute force solution for Longest Consecutive Sequence?

Yes. Brute force (extend each value by searching) takes O(n³) time and O(1) space. Treat every value as a possible start and keep looking for the next integer by scanning the whole array, counting how far the run goes.

Which edge cases should I test for Longest Consecutive Sequence?

Empty array; Duplicates inside a run, which must be counted once; Negative numbers and runs that cross zero; All values equal: the answer is 1; Values far apart, so every run has length 1.