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
    
    

All Problems

All Solutions