Question

Formatted question description: https://leetcode.ca/all/128.html

128. Longest Consecutive Sequence

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

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

@tag-array

Algorithm

For every num existed in set, try to probe to right to see if following numbers are also in set, and record longest possible sequence.

Code

Java

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Longest_Consecutive_Sequence {

    // Time complexity : O(n)
    // Space complexity : O(n)
    class Solution_oN {
        public int longestConsecutive(int[] nums) {

            Set<Integer> hs = new HashSet<Integer>();

            // remove duplicates
            for (int num : nums) {
                hs.add(num);
            }

            int longestStreak = 0;

            for (int num : hs) {
                if (!hs.contains(num - 1)) {
                    int currentNum = num;
                    int currentStreak = 1;

                    while (hs.contains(currentNum + 1)) {
                        currentNum += 1;
                        currentStreak += 1;
                    }

                    longestStreak = Math.max(longestStreak, currentStreak);
                }
            }

            return longestStreak;
        }
    }

    class Solution_sort {
        public int longestConsecutive(int[] nums) {
            if (nums.length == 0) {
                return 0;
            }

            Arrays.sort(nums);

            int longestStreak = 1;
            int currentStreak = 1;

            for (int i = 1; i < nums.length; i++) {
                if (nums[i] != nums[i-1]) {
                    if (nums[i] == nums[i-1]+1) {
                        currentStreak += 1;
                    }
                    else {
                        longestStreak = Math.max(longestStreak, currentStreak);
                        currentStreak = 1;
                    }
                }
            }

            return Math.max(longestStreak, currentStreak);
        }
    }
}

// OJ: https://leetcode.com/problems/longest-consecutive-sequence/
// Time: O(N)
// Space: O(N)
// Ref: https://leetcode.com/problems/longest-consecutive-sequence/discuss/41088/Possibly-shortest-cpp-solution-only-6-lines.
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_map<int, int> m;
        int ans = 0;
        for (int n : nums) {
            if (m[n]) continue;
            ans = max(ans, m[n] = m[n - m[n - 1]] = m[n + m[n + 1]] = m[n - 1] + m[n + 1] + 1);
        }
        return ans;
    }
};

class Solution(object):
  def longestConsecutive(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    ans = 0
    s = set(nums)
    for num in nums:
      if num in s:
        s.discard(num)
        cnt = 1
        right = num + 1
        left = num - 1
        while left in s:
          s.discard(left)
          cnt += 1
          left -= 1
        while right in s:
          s.discard(right)
          cnt += 1
          right += 1
        ans = max(ans, cnt)
    return ans

128 - Longest Consecutive Sequence

Question

Algorithm

Code

All Problems

All Solutions