[LeetCode] 128. Longest Consecutive Sequence

Posted on | In

Problem

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example:

1
2
3
Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Explanation

  1. Since it’s O(n) complexity, so we use a set to store all the numbers. Then, we iterate the array’s number, if it is in the set, then we remove it from the set and create two variables pre and nex to record its previous continuous number and next continuous number. Then, we find if pre in the set, if it is in the set, then we remove it from the set and update --pre until pre is not in the set. Similar to nex, if it is in the set, then we remove it and update ++nex until nex is not in the set. Now, the current number’s longest continuous sequence will be nex-pre-1.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        Set<Integer> set = new HashSet<>();
        for (int num : nums) set.add(num);
        int res = 0;
        for (int num : nums) {
            if (set.remove(num)) {
                int pre = num-1;
                int nex = num+1;
                while (set.remove(pre)) --pre;
                while (set.remove(nex)) ++nex;
                res = Math.max(res, nex-pre-1);
            }
        }

        return res;
    }
}