Longest Consecutive Sequence LeetCode Solution

Minimum Cost to Merge Stones
Share:

Longest Consecutive Sequence Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Example 1:

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

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

Constraints:

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109

Longest Consecutive Sequence Solutions

Time: O(n)
Space: O(n)

C++

class Solution {
 public:
  int longestConsecutive(vector<int>& nums) {
    int ans = 0;
    unordered_set<int> seen{begin(nums), end(nums)};

    for (int num : nums) {
      // num is the start of a sequence
      if (seen.count(num - 1))
        continue;
      int length = 1;
      while (seen.count(++num))
        ++length;
      ans = max(ans, length);
    }

    return ans;
  }
};

Java

 class Solution {
  public int longestConsecutive(int[] nums) {
    int ans = 0;
    Set<Integer> seen = Arrays.stream(nums).boxed().collect(Collectors.toSet());

    for (int num : nums) {
      // num is the start of a sequence
      if (seen.contains(num - 1))
        continue;
      int length = 1;
      while (seen.contains(++num))
        ++length;
      ans = Math.max(ans, length);
    }

    return ans;
  }
}

Python


class Solution:
  def longestConsecutive(self, nums: List[int]) -> int:
    ans = 0
    seen = set(nums)

    for num in nums:
      if num - 1 in seen:
        continue
      length = 0
      while num in seen:
        num += 1
        length += 1
      ans = max(ans, length)

    return ans

Watch Tutorial

Checkout more Solutions here

Leave a Comment

Your email address will not be published. Required fields are marked *

x