Longest Consecutive Sequence

Microsoft Interview Question

Problem Overview

Difficulty: Medium
LeetCode Pattern: Arrays & Hashing

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

Input: 
· nums = [100,4,200,1,3,2]
Output: 
· 4
Explanation: 
· Longest Seq. = [1, 2, 3, 4]
· It's length is 4

---

Step 1: Clarify Requirements

• Can input be empty?

  • Yes, return 0.

• Can input include negatives?

  • Yes.

• Can input contain duplicates?

  • Yes.

---

Step 2: Discuss Approaches

1/ Sort + Linear Scan (Brute Force ⚠️)

• Logic:

  • Sort the array

  • Iterate through it

  • Count consecutive sequences

  • Track their lengths

  • Keep max length

• Big O:

  • Time Complexity: O(n·logn)

  • Space Complexity: O(n)

---

2/ Set + Linear Scan (Optimal ✅)

• Logic:

  • Put all nums in a set (O(1) lookups)

  • For each num in set:

    • Check if num-1 is not in set

    • If not, it’s start of a sequence

  • For each sequence start:

    • Count consecutive numbers

    • And keep track of max length

• Big O:

  • Time Complexity: O(n)

  • Space Complexity: O(n)

---

Step 3: Write Code (Optimal)

Python

---

Java

---

C++

---

Step 4: Answer Follow-Ups

• What if duplicates exist?

  • Set removes them automatically.

• Can we return the sequence itself?

  • Yes, keep track of start.

  • Build the sequence after scanning.