128. Longest Consecutive Sequence

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

Your algorithm should run in O(n) complexity.

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.

Key: see array as chunks of consecutive numbers, keep & increase length while traversing the array.

Java Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int longestConsecutive(int[] nums) {
        Integer[] newNums = new Integer[nums.length];
        for (int i = 0; i < nums.length; ++i) {
            newNums[i] = Integer.valueOf(nums[i]);
        }
        Set<Integer> s = new HashSet<>(Arrays.asList(newNums));
        int res = 0;
        for (int i : s) {
            if (!s.contains(i-1)) {
                int j = i + 1;
                while (s.contains(j)) {
                    ++j;
                }
                res = Math.max(res, j - i);
            }
        }
        return res;
    }
}

Achtung: ⚠️
  1. Generic: Set<T>, ArrayList<T> …. T can only be Object, not primitive types;
  2. e.g. Set<Integer>✅, Set<int>❌

  3. pre-process: 

    1
    2
    3
    4
    5
    Integer[] newNums = new Integer[nums.length];
    for (int i = 0; i < nums.length; ++i) {
        newNums[i] = Integer.valueOf(nums[i]);
    }
    Set<Integer> s = new HashSet<>(Arrays.asList(newNums));

  4. This is how to convert an Array to a Set in java: create an Integer[] array from int[] array, then transform to a List via Arrays.asList(Integer[] xxx), then a HashSet based on that.

  5. 基礎は非常に重要です。

Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums = set(nums)
        res = 0
        for i in nums:
            if i - 1 not in nums:
                y = i + 1
                while y in nums:
                    y += 1
                res = max(res, y - i)
        return res