DSA 450 Notes

Problem Statement

Given an unsorted array of integers, find the length of the longest consecutive elements sequence. The sequence doesn't need to be contiguous in the array.

Example:

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

Approach 1: Brute Force

Intuition

For each element, check how long a consecutive sequence can be formed starting from that element.

Algorithm

For each element x in array
Check if x+1, x+2, x+3, ... exist in array
Count the length of consecutive sequence
Track maximum length

java

public class Solution {
    private boolean contains(int[] nums, int target) {
        for (int num : nums) {
            if (num == target) return true;
        }
        return false;
    }
    
    public int longestConsecutiveBruteForce(int[] nums) {
        if (nums.length == 0) return 0;
        
        int maxLength = 0;
        
        for (int num : nums) {
            int current = num;
            int length = 1;
            
            while (contains(nums, current + 1)) {
                current++;
                length++;
            }
            
            maxLength = Math.max(maxLength, length);
        }
        
        return maxLength;
    }
}

Complexity Analysis

Time Complexity: O(n³) - For each element, search takes O(n), sequence can be O(n) long
Space Complexity: O(1) - No extra space used

Approach 2: Sorting

Intuition

Sort the array first. Consecutive elements will be adjacent, making it easy to count sequences.

Algorithm

Sort the array
Traverse and count consecutive elements
Handle duplicates (skip them)
Track maximum sequence length

java

import java.util.*;

public class Solution {
    public int longestConsecutiveSorting(int[] nums) {
        if (nums.length == 0) return 0;
        
        Arrays.sort(nums);
        
        int maxLength = 1;
        int currentLength = 1;
        
        for (int i = 1; i < nums.length; i++) {
            // Skip duplicates
            if (nums[i] == nums[i - 1]) continue;
            
            // Check if consecutive
            if (nums[i] == nums[i - 1] + 1) {
                currentLength++;
            } else {
                maxLength = Math.max(maxLength, currentLength);
                currentLength = 1;
            }
        }
        
        return Math.max(maxLength, currentLength);
    }
}

Complexity Analysis

Time Complexity: O(n log n) - Dominated by sorting
Space Complexity: O(1) or O(n) - Depends on sorting implementation

Approach 3: Using HashSet (Optimal)

Intuition

Use a HashSet for O(1) lookups. For each number, only start counting a sequence if it's the beginning of a sequence (i.e., num-1 doesn't exist).

Algorithm

Add all numbers to a HashSet
For each number, check if it's the start of a sequence (num-1 not in set)
If it's a start, count consecutive numbers
Track maximum length

java

import java.util.*;

public class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) return 0;
        
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }
        
        int maxLength = 0;
        
        for (int num : numSet) {
            // Only start counting if this is the beginning of a sequence
            if (!numSet.contains(num - 1)) {
                int current = num;
                int length = 1;
                
                // Count consecutive numbers
                while (numSet.contains(current + 1)) {
                    current++;
                    length++;
                }
                
                maxLength = Math.max(maxLength, length);
            }
        }
        
        return maxLength;
    }
}

Complexity Analysis

Time Complexity: O(n) - Each element is visited at most twice
Space Complexity: O(n) - HashSet storage

Visual Example

For array [100, 4, 200, 1, 3, 2]:

HashSet: {100, 4, 200, 1, 3, 2}

Check 100:
  100 - 1 = 99 not in set → Start of sequence
  100 + 1 = 101 not in set → Length = 1

Check 4:
  4 - 1 = 3 in set → Not start of sequence, skip

Check 200:
  200 - 1 = 199 not in set → Start of sequence
  200 + 1 = 201 not in set → Length = 1

Check 1:
  1 - 1 = 0 not in set → Start of sequence
  1 + 1 = 2 in set → continue
  2 + 1 = 3 in set → continue
  3 + 1 = 4 in set → continue
  4 + 1 = 5 not in set → Length = 4

Check 3: 3 - 1 = 2 in set → Skip
Check 2: 2 - 1 = 1 in set → Skip

Maximum length = 4

Alternative: Union-Find Approach

Key Takeaways

HashSet enables O(1) lookups, transforming O(n³) to O(n)
Key optimization: Only start counting from sequence beginnings
This ensures each element is processed at most twice (once for checking start, once in sequence)
Sorting approach is simpler but O(n log n)
Union-Find is an alternative O(n) solution with different tradeoffs
Handle duplicates - they don't affect sequence length

Find longest consecutive subsequence

Problem Statement

Approach 1: Brute Force

Intuition

Algorithm

Complexity Analysis

Approach 2: Sorting

Intuition

Algorithm

Complexity Analysis

Approach 3: Using HashSet (Optimal)

Intuition

Algorithm

Complexity Analysis

Visual Example

Alternative: Union-Find Approach

Key Takeaways