0128_longest_consecutive_sequence.html

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>LC 128: Longest Consecutive Sequence - Algorithm Visualization</title>
    <link rel="stylesheet" href="styles.css">
    <script src="https://d3js.org/d3.v7.min.js"></script>
</head>
<body>
    <div class="container">
        <div class="problem-info">
            <h1><span class="problem-number">#128</span> Longest Consecutive Sequence</h1>
            <p>Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence. Must run in O(n) time.</p>
            <div class="problem-meta">
                <span class="meta-tag">📁 Array</span>
                <span class="meta-tag">🔤 Hash Set</span>
                <span class="meta-tag">⏱️ O(n)</span>
            </div>
            <div class="file-ref">
                📄 Python: <code>python/0128_longest_consecutive_sequence/0128_longest_consecutive_sequence.py</code>
            </div>
            </div>

        <div class="explanation-panel">
            <h4>🧠 How It Works (Layman's Terms)</h4>
            <p>Imagine you have scattered puzzle pieces numbered 1, 2, 3, 4, 100, 200. You want to find the longest chain of consecutive numbers.</p>
            <ul>
                <li><strong>Step 1:</strong> Put all numbers in a set for fast lookup</li>
                <li><strong>Step 2:</strong> For each number, check if it's the START of a sequence (no number before it)</li>
                <li><strong>Step 3:</strong> If it's a start, count how far the sequence goes (1→2→3→4...)</li>
                <li><strong>Step 4:</strong> Track the longest chain found</li>
            </ul>
            <p>The key insight: Only start counting from sequence starts (where n-1 doesn't exist). This ensures O(n) time!</p>
        </div>


        <div class="visualization-section">
            <h3>🎬 Step-by-Step Visualization</h3>
            
            <div class="controls">
                <button class="btn btn-primary" id="stepBtn" onclick="step()">Step</button>
                <button class="btn btn-success" id="autoBtn" onclick="toggleAuto()">Auto Run</button>
                <button class="btn btn-warning" onclick="reset()">Reset</button>
            </div>

            <div class="status-message" id="statusMessage">
                Click "Step" or "Auto Run" to start visualization
            </div>

            <div class="variable-display">
                <div class="variable-box">
                    <div class="variable-name">Current Number</div>
                    <div class="variable-value" id="currentNum">-</div>
                </div>
                <div class="variable-box">
                    <div class="variable-name">Current Streak</div>
                    <div class="variable-value" id="currentStreak">0</div>
                </div>
                <div class="variable-box">
                    <div class="variable-name">Longest Streak</div>
                    <div class="variable-value" id="longestStreak" style="color: #4caf50;">0</div>
                </div>
            </div>

            <div class="array-section">
                <div class="array-label">📥 Input Array (as Set):</div>
                <div class="array-container" id="setContainer"></div>
            </div>

            <div class="array-section">
                <div class="array-label">🔗 Current Sequence Being Built:</div>
                <div class="array-container" id="sequenceContainer">
                    <div style="color: #999; padding: 10px;">Sequence will appear here</div>
                </div>
            </div>
        </div>
        <div class="code-section">
            <h3>💻 Python Solution</h3>
            <div class="code-block">
                <pre>from typing import List

"""
LeetCode Longest Consecutive Sequence

Problem from LeetCode: https://leetcode.com/problems/longest-consecutive-sequence/

Description:
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
"""

class Solution:
    def longest_consecutive(self, nums: List[int]) -&gt; int:
        """
        Find the length of the longest consecutive sequence.
        Uses a hash set to achieve O(n) time complexity.
        
        Args:
            nums: Unsorted array of integers
            
        Returns:
            int: Length of longest consecutive sequence
        """
        if not nums:
            return 0
            
        # Convert the list to a set for O(1) lookups
        num_set = set(nums)
        longest_streak = 0
        
        for num in num_set:
            # Only check sequences starting from the smallest number in the sequence
            # Skip if there's already a smaller number before the current number
            if num - 1 not in num_set:
                current_num = num
                current_streak = 1
                
                # Count consecutive numbers
                while current_num + 1 in num_set:
                    current_num += 1
                    current_streak += 1
                    
                # Update the longest streak
                longest_streak = max(longest_streak, current_streak)
                
        return longest_streak
    
    def longest_consecutive_union_find(self, nums: List[int]) -&gt; int:
        """
        Find the longest consecutive sequence using Union-Find.
        
        Args:
            nums: Unsorted array of integers
            
        Returns:
            int: Length of longest consecutive sequence
        """
        if not nums:
            return 0
            
        # Create parent dictionary for Union-Find
        parent = {}
        size = {}
        
        # Initialize parent and size for each number
        for num in nums:
            parent[num] = num
            size[num] = 1
            
        # Find function for Union-Find with path compression
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
            
        # Union function
        def union(x, y):
            root_x = find(x)
            root_y = find(y)
            
            if root_x != root_y:
                # Make the larger root the parent of the smaller root
                if size[root_x] &lt; size[root_y]:
                    parent[root_x] = root_y
                    size[root_y] += size[root_x]
                else:
                    parent[root_y] = root_x
                    size[root_x] += size[root_y]
                    
        # Union consecutive numbers
        num_set = set(nums)
        for num in num_set:
            if num + 1 in num_set:
                union(num, num + 1)
                
        # Find the maximum size
        max_size = 0
        for num in num_set:
            if parent[num] == num:  # Only consider roots
                max_size = max(max_size, size[num])
                
        return max_size

if __name__ == '__main__':
    # Example usage based on LeetCode sample
    solution = Solution()
    
    # Example 1
    nums1 = [100, 4, 200, 1, 3, 2]
    result1 = solution.longest_consecutive(nums1)
    print(f"Example 1: nums={nums1}, result={result1}")  # Expected output: 4
    
    # Example 2
    nums2 = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
    result2 = solution.longest_consecutive(nums2)
    print(f"Example 2: nums={nums2}, result={result2}")  # Expected output: 9
    
    # Edge case
    nums3 = []
    result3 = solution.longest_consecutive(nums3)
    print(f"Edge case: nums={nums3}, result={result3}")  # Expected output: 0
    
    # Compare with Union-Find approach
    print("\nUsing Union-Find approach:")
    print(f"Example 1: {solution.longest_consecutive_union_find(nums1)}")
    print(f"Example 2: {solution.longest_consecutive_union_find(nums2)}")
</pre>
            </div>
        </div>
    </div>

    <script>
        const nums = [100, 4, 200, 1, 3, 2];
        const numSet = new Set(nums);
        const sortedNums = Array.from(numSet).sort((a, b) => a - b);
        let setIndex = 0;
        let currentNum = null;
        let currentStreak = 0;
        let longestStreak = 0;
        let currentSequence = [];
        let phase = 'check'; // 'check' or 'extend'
        let autoInterval = null;

        function init() {
            renderSet();
            document.getElementById('currentNum').textContent = '-';
            document.getElementById('currentStreak').textContent = '0';
            document.getElementById('longestStreak').textContent = '0';
            document.getElementById('sequenceContainer').innerHTML = '<div style="color: #999; padding: 10px;">Sequence will appear here</div>';
        }

        function renderSet() {
            const container = document.getElementById('setContainer');
            container.innerHTML = '';
            sortedNums.forEach((num) => {
                const box = document.createElement('div');
                box.className = 'array-box';
                box.id = `set-${num}`;
                box.textContent = num;
                container.appendChild(box);
            });
        }

        function renderSequence() {
            const container = document.getElementById('sequenceContainer');
            container.innerHTML = '';
            
            if (currentSequence.length === 0) {
                container.innerHTML = '<div style="color: #999; padding: 10px;">Sequence will appear here</div>';
                return;
            }

            currentSequence.forEach((num, idx) => {
                if (idx > 0) {
                    const arrow = document.createElement('span');
                    arrow.textContent = '→';
                    arrow.style.fontSize = '1.5em';
                    arrow.style.color = '#4caf50';
                    container.appendChild(arrow);
                }
                const box = document.createElement('div');
                box.className = 'array-box';
                box.style.background = '#e8f5e9';
                box.style.borderColor = '#4caf50';
                box.textContent = num;
                container.appendChild(box);
            });
        }

        function clearHighlights() {
            sortedNums.forEach(num => {
                const el = document.getElementById(`set-${num}`);
                if (el) {
                    el.classList.remove('highlight', 'current', 'visited');
                    el.style.background = '';
                    el.style.borderColor = '';
                }
            });
        }

        function step() {
            if (setIndex >= sortedNums.length) {
                document.getElementById('statusMessage').className = 'status-message success';
                document.getElementById('statusMessage').textContent = 
                    `✅ Done! Longest consecutive sequence has length ${longestStreak}`;
                document.getElementById('stepBtn').disabled = true;
                stopAuto();
                return;
            }

            if (phase === 'check') {
                const num = sortedNums[setIndex];
                clearHighlights();
                document.getElementById(`set-${num}`).classList.add('highlight');
                document.getElementById('currentNum').textContent = num;

                // Check if this is start of sequence (num-1 not in set)
                if (!numSet.has(num - 1)) {
                    // Start of a new sequence
                    currentNum = num;
                    currentStreak = 1;
                    currentSequence = [num];
                    renderSequence();
                    document.getElementById('currentStreak').textContent = currentStreak;
                    document.getElementById(`set-${num}`).style.background = '#e8f5e9';
                    document.getElementById(`set-${num}`).style.borderColor = '#4caf50';
                    
                    document.getElementById('statusMessage').textContent = 
                        `${num} is a sequence START (${num-1} not in set). Starting new sequence...`;
                    
                    // Check if we can extend
                    if (numSet.has(num + 1)) {
                        phase = 'extend';
                    } else {
                        // Single number sequence
                        longestStreak = Math.max(longestStreak, currentStreak);
                        document.getElementById('longestStreak').textContent = longestStreak;
                        setIndex++;
                    }
                } else {
                    document.getElementById('statusMessage').textContent = 
                        `${num} is NOT a sequence start (${num-1} exists). Skipping...`;
                    document.getElementById(`set-${num}`).style.background = '#f5f5f5';
                    setIndex++;
                }
            } else if (phase === 'extend') {
                currentNum++;
                if (numSet.has(currentNum)) {
                    currentStreak++;
                    currentSequence.push(currentNum);
                    renderSequence();
                    document.getElementById('currentNum').textContent = currentNum;
                    document.getElementById('currentStreak').textContent = currentStreak;
                    
                    document.getElementById(`set-${currentNum}`).classList.add('highlight');
                    document.getElementById(`set-${currentNum}`).style.background = '#e8f5e9';
                    document.getElementById(`set-${currentNum}`).style.borderColor = '#4caf50';
                    
                    document.getElementById('statusMessage').textContent = 
                        `Found ${currentNum} in set! Sequence extended to length ${currentStreak}`;
                    
                    if (!numSet.has(currentNum + 1)) {
                        // Sequence ends
                        longestStreak = Math.max(longestStreak, currentStreak);
                        document.getElementById('longestStreak').textContent = longestStreak;
                        phase = 'check';
                        setIndex++;
                    }
                } else {
                    // Should not happen in this logic, but safety
                    longestStreak = Math.max(longestStreak, currentStreak);
                    document.getElementById('longestStreak').textContent = longestStreak;
                    phase = 'check';
                    setIndex++;
                }
            }
        }

        function toggleAuto() {
            if (autoInterval) {
                stopAuto();
            } else {
                document.getElementById('autoBtn').textContent = 'Pause';
                autoInterval = setInterval(() => {
                    if (setIndex >= sortedNums.length) {
                        step();
                        stopAuto();
                    } else {
                        step();
                    }
                }, 800);
            }
        }

        function stopAuto() {
            if (autoInterval) {
                clearInterval(autoInterval);
                autoInterval = null;
            }
            document.getElementById('autoBtn').textContent = 'Auto Run';
        }

        function reset() {
            stopAuto();
            setIndex = 0;
            currentNum = null;
            currentStreak = 0;
            longestStreak = 0;
            currentSequence = [];
            phase = 'check';
            document.getElementById('stepBtn').disabled = false;
            document.getElementById('statusMessage').className = 'status-message';
            document.getElementById('statusMessage').textContent = 'Click "Step" or "Auto Run" to start visualization';
            init();
        }

        init();
    </script>
</body>
</html>