What is the time complexity of Longest Consecutive Sequence?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Longest Consecutive Sequence?

This problem uses Array, Hash Table, Union Find. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Longest Consecutive Sequence?

Insight 1: Using a set data structure allows for O(1) average time complexity for checking the existence of an element, which is essential for achieving the O(n) time complexity requirement. Insight 2: To avoid redundant checks, we only start counting a sequence from the smallest number in that sequence (i.e., a number where `num - 1` is not present in the set).

Which companies ask LeetCode 128. Longest Consecutive Sequence in interviews?

This problem is frequently asked at Atlassian, ByteDance, Cisco, DE Shaw, DeltaX and 25 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Longest Consecutive Sequence - LeetCode 128 Solution

Q: How to solve Longest Consecutive Sequence?

The provided solution utilizes a set to efficiently check for the presence of numbers. The algorithm iterates through the numbers in the set. For each number, it checks if the number minus one is also in the set. If not, this indicates that the current number is the potential start of a consecutive sequence. The algorithm then iterates upwards from this number, checking for consecutive numbers and incrementing a streak counter until a break in the consecutive sequence is found. The longest streak seen so far is updated accordingly.

Longest Consecutive Sequence - Complete Solution Guide

Longest Consecutive Sequence is LeetCode problem 128, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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 Example 3: Input: nums = [1,0,1,2] Output: 3 Constraints: 0 <= nums.length <= 10 5 -10 9 <= nums[i] <= 10 9

Detailed Explanation

The problem asks us to find the length of the longest consecutive sequence of integers within an unsorted array of integers. The consecutive sequence doesn't need to be contiguous in the input array. The crucial requirement is that the solution must run in O(n) time complexity. For example, given the input [100, 4, 200, 1, 3, 2], the longest consecutive sequence is [1, 2, 3, 4], so the output should be 4.

Solution Approach

The provided solution utilizes a set to efficiently check for the presence of numbers. The algorithm iterates through the numbers in the set. For each number, it checks if the number minus one is also in the set. If not, this indicates that the current number is the potential start of a consecutive sequence. The algorithm then iterates upwards from this number, checking for consecutive numbers and incrementing a streak counter until a break in the consecutive sequence is found. The longest streak seen so far is updated accordingly.

Step-by-Step Algorithm

Step 1: Create a set from the input array `nums`. This removes duplicates and allows for O(1) lookups.
Step 2: Initialize a variable `longest_streak` to 0 to store the maximum consecutive sequence length found so far.
Step 3: Iterate through each `num` in the set.
Step 4: For each `num`, check if `num - 1` is present in the set. If it is not present, this means `num` is the potential start of a new consecutive sequence.
Step 5: If `num - 1` is not present, initialize `current_num` to `num` and `current_streak` to 1.
Step 6: While `current_num + 1` is present in the set, increment `current_num` and `current_streak`.
Step 7: After the inner while loop finishes, update `longest_streak` to the maximum of `longest_streak` and `current_streak`.
Step 8: After iterating through all numbers in the set, return `longest_streak`.

Key Insights

Insight 1: Using a set data structure allows for O(1) average time complexity for checking the existence of an element, which is essential for achieving the O(n) time complexity requirement.
Insight 2: To avoid redundant checks, we only start counting a sequence from the smallest number in that sequence (i.e., a number where `num - 1` is not present in the set).
Insight 3: Although there is a while loop within the for loop, each number is only visited once as the start of the sequence. This ensures the O(n) time complexity.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Topics

This problem involves: Array, Hash Table, Union Find.

Companies

Asked at: Atlassian, ByteDance, Cisco, DE Shaw, DeltaX, EPAM Systems, Flipkart, Google, IBM, Infosys, Lyft, Oracle, PayPal, Paytm, PhonePe, Roblox, SAP, ServiceNow, Swiggy, TikTok, Turing, UKG, Uber, Walmart Labs, Wissen Technology, Yahoo, Yandex, Zepto, Zoho, tcs.

Longest Consecutive Sequence | LeetCode 128

Medium

Array Hash Table Union Find

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

Solution Code

Available in:

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

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }

        int longestStreak = 0;

        for (int num : numSet) {
            if (!numSet.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;

                while (numSet.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }

                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }

        return longestStreak;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 128: Longest Consecutive Sequence - Detailed explanation and solution approaches.

Topics

Array Hash Table Union Find

Companies

AtlassianByteDanceCiscoDE ShawDeltaXEPAM SystemsFlipkartGoogle

Stats

Difficulty:Medium

Languages:4

Companies:30

Problem #:128

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

8 steps

1
Step 1: Create a set from the input array `nums`. This removes duplicates and allows for O(1) lookups.
2
Step 2: Initialize a variable `longest_streak` to 0 to store the maximum consecutive sequence length found so far.
3
Step 3: Iterate through each `num` in the set.
4
Step 4: For each `num`, check if `num - 1` is present in the set. If it is not present, this means `num` is the potential start of a new consecutive sequence.
5
Step 5: If `num - 1` is not present, initialize `current_num` to `num` and `current_streak` to 1.
6
Step 6: While `current_num + 1` is present in the set, increment `current_num` and `current_streak`.
7
Step 7: After the inner while loop finishes, update `longest_streak` to the maximum of `longest_streak` and `current_streak`.
8
Step 8: After iterating through all numbers in the set, return `longest_streak`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The algorithm iterates through the input array once to create the set, which takes O(n) time. The outer loop iterates through the set, which in the worst case has n elements. The inner while loop iterates at most n times in total across all iterations of the outer loop because each number is only visited once as the start of the sequence. Therefore, the overall time complexity is O(n). The space complexity is O(n) because the set stores at most n elements.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Sorting

Sort the array first and then iterate through it to find consecutive sequences. Sorting typically uses O(n log n) time complexity.

Time: O(n log n)Space: O(1) if done in-place, O(n) otherwise

Trade-offs: This approach is simpler to implement but doesn't meet the O(n) time complexity requirement. It's suitable when the time complexity constraint is relaxed.

Union Find

Treat each number as a separate set. Iterate through the array, and for each number, check if num+1 and num-1 are in the array. If they are, perform union operation to merge the current number's set with the sets containing num+1 and num-1.

Time: O(n) amortizedSpace: O(n)

Trade-offs: Union Find can be more complex to implement, but is more suitable if you need to track which numbers are in the same consecutive sequence, rather than only calculate the maximum length.

✨

Key Insights

1Insight 1: Using a set data structure allows for O(1) average time complexity for checking the existence of an element, which is essential for achieving the O(n) time complexity requirement.
2Insight 2: To avoid redundant checks, we only start counting a sequence from the smallest number in that sequence (i.e., a number where `num - 1` is not present in the set).
3Insight 3: Although there is a while loop within the for loop, each number is only visited once as the start of the sequence. This ensures the O(n) time complexity.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

Edge Cases

Edge case 1: Empty input array. The code handles this correctly by returning 0 as the `longest_streak` is initialized to 0 and the loop never executes.
Edge case 2: Array with duplicate numbers. The set data structure eliminates duplicate numbers, ensuring that each unique number is only processed once, preventing incorrect sequence length calculations.
Edge case 3: Array with all identical numbers. The outer loop iterates through only one instance of the number (due to the set), and the inner loop doesn't run because the next consecutive number isn't present, resulting in a longest streak of 1.
Edge case 4: Large input values. The hash set implementations (Python's `set`, Java's `HashSet`, C++'s `unordered_set`, and the C hash set) handle arbitrary integer values within the constraints efficiently. No integer overflow occurs in the core logic because it only involves addition and comparison.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Failing to use a set or hash table. Using a linear search to check for the presence of numbers would result in an O(n^2) time complexity, violating the problem constraint.

✗Common mistake 2: Not handling duplicates correctly. If duplicates are not removed, the algorithm may overcount the length of consecutive sequences.

✗Common mistake 3: Incorrectly assuming the sequence must be contiguous in the original array. The problem asks for the longest *consecutive* sequence, meaning the numbers must be in order, but not necessarily adjacent in the input array.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Data analysis where identifying consecutive data points is important, such as finding the longest streak of consecutive days with increasing sales.

🏦Real-world scenario 2: Network routing where identifying a sequence of consecutive available IP addresses is necessary for assigning a block of addresses to a new client.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Consider multiple approaches before coding. Mentioning alternatives shows breadth of knowledge.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: October 7, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 13

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 6

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

What are the trade-offs of using a hash table?

Hash tables provide O(1) average-case lookup, insertion, and deletion, making them ideal for frequency counting and duplicate detection. However, they use O(n) extra space and may degrade to O(n) time in worst-case scenarios with hash collisions. Always consider if the space trade-off is acceptable.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Longest Consecutive Sequence"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether hash table techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?