algoadvance

Leetcode 128. Longest Consecutive Sequence

Problem Statement

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

Example:

Constraints:

Clarifying Questions

  1. Can the array contain duplicates?
    • No. The prompt specifies an array of integers, and unique property isn’t mentioned, so they can contain duplicates.
  2. What should be returned if the array is empty?
    • Return 0.

Code

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

public class LongestConsecutiveSequence {
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) return 0;
        
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }
        
        int longestStreak = 0;
        
        for (int num : numSet) {
            if (!numSet.contains(num - 1)) {  // only look for the start of a sequence
                int currentNum = num;
                int currentStreak = 1;
                
                while (numSet.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }
                
                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }
        
        return longestStreak;
    }

    public static void main(String[] args) {
        LongestConsecutiveSequence solution = new LongestConsecutiveSequence();
        int[] nums = {100, 4, 200, 1, 3, 2};
        System.out.println(solution.longestConsecutive(nums));  // Output: 4
    }
}

Strategy

  1. Use a HashSet to achieve O(1) time complexity for element lookup.
  2. Iterate through the array and add every element to the HashSet.
  3. Iterate through the HashSet:
    • For each number, check if it’s the start of a sequence (i.e., num - 1 is not in the Set).
    • If it’s the start, count the length of the sequence by incrementing the number and checking if the next number exists in the Set.
  4. Keep track of the longest sequence found.
  5. Return the length of the longest sequence.

Time Complexity

Thus, the overall time complexity is O(n), where n is the number of elements in the array. The space complexity is also O(n) due to the extra space required for the HashSet.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI