012 — Longest Consecutive Sequence¶

Source¶

Original source: Classic seen-set / smart-start exercise
Platform: LeetCode — https://leetcode.com/problems/longest-consecutive-sequence/
Topic: hash set
Difficulty: Medium
Pattern: seen-set + smart start
Basic idea inherited from: Contains Duplicate — set-এ ভরে O(1) membership

1. Problem in simple words¶

একটা সংখ্যার array nums দেওয়া আছে (সাজানো নয়, পুনরাবৃত্তি থাকতে পারে)। এমন পরপর পূর্ণসংখ্যার (consecutive) সবচেয়ে লম্বা ধারা-র দৈর্ঘ্য বের করতে হবে — তবে শর্ত: পুরো কাজ O(n) সময়ে, অর্থাৎ sort করা যাবে না (sort O(n log n))।

nums = [100, 4, 200, 1, 3, 2]
পরপর ধারা: 1, 2, 3, 4 → দৈর্ঘ্য 4
উত্তর: 4

2. Which basic idea does this inherit from?¶

এটা seen-set pattern (Contains Duplicate, #2)-এর উপর দাঁড়ানো। সেখানে শিখেছ সব value একটা set-এ ভরলে "এটা আছে কি?" প্রশ্নের উত্তর O(1)। এখানে সেই set-এর উপর একটা চালাক সংযোজন — smart start — যাতে প্রতিটা ধারা ঠিক একবারই গোনা হয়। ../patterns.md-তে এটা Pattern 4-এর extension।

3. What is the hidden math or logic?¶

লুকানো logic: একটা পরপর-ধারার শুরু সেই সংখ্যা x, যার ঠিক আগের সংখ্যা x-1 set-এ নেই। শুধু এমন শুরু-সংখ্যা থেকেই ধারা গোনা শুরু করলে, প্রতিটা ধারা মাত্র একবার গোনা হয়। ফলে সব গোনা মিলিয়ে মোট কাজ O(n)-এ আটকে থাকে — যদিও ভেতরে একটা while loop আছে।

4. Which data structure is needed?¶

একটা hash set (Python-এ set)। দুটো জিনিস দরকার: (ক) পুনরাবৃত্তি ফেলে distinct value রাখা, আর (খ) "x-1 আছে?" ও "x+length আছে?" — এই membership query O(1)-এ করা। set দুটোই দেয়।

5. Why this data structure fits¶

পুরো algorithm-টার প্রাণ হলো অসংখ্য "এই সংখ্যাটা আছে কি?" প্রশ্ন। set গড়ে O(1)-এ উত্তর দেয়, তাই n বার এমন প্রশ্ন করলেও মোট O(n)। List হলে প্রতিটা membership check O(n) হতো, পুরোটা O(n^2) — sort-এর চেয়েও খারাপ। set-ই এখানে O(n)-এর একমাত্র সহজ পথ।

6. Real-life analogy¶

ভাবো একটা ঘরে অনেকজন, প্রত্যেকের গায়ে একটা নম্বর। তুমি সবচেয়ে লম্বা "পরপর নম্বরের সারি" বানাতে চাও। সবাইকে বারবার জিজ্ঞেস না করে নিয়ম করো: শুধু সেই-ই সারি শুরু করবে, যার ঠিক এক-কম নম্বরওয়ালা কেউ ঘরে নেই (সে-ই স্বাভাবিক "নেতা")। নেতা তারপর এক-বেশি, আরও এক-বেশি ডাকতে থাকে যতক্ষণ পায়। প্রতিটা সারির একজনই নেতা, তাই কেউ দুবার গোনা হয় না।

7. Visual explanation¶

nums = [100, 4, 200, 1, 3, 2] → num_set = {1,2,3,4,100,200}। শুধু run-শুরু থেকে গুনি:

x=1   : 0 in set? না → শুরু। 2,3,4 আছে → length 4
x=2   : 1 in set? হ্যাঁ → শুরু নয়, skip
x=3   : 2 in set? হ্যাঁ → skip
x=4   : 3 in set? হ্যাঁ → skip
x=100 : 99 in set? না → শুরু। 101 নেই → length 1
x=200 : 199 in set? না → শুরু। 201 নেই → length 1
সবচেয়ে লম্বা: 4

8. Example input and output¶

Input : [100, 4, 200, 1, 3, 2]          Output: 4    (1,2,3,4)
Input : [0,3,7,2,5,8,4,6,0,1]           Output: 9    (0..8)
Input : []                              Output: 0
Input : [1]                             Output: 1
Edge  : [1, 2, 0, 1]                    Output: 3    (0,1,2; পুনরাবৃত্তি গোনায় আসে না)

9. Brute force thinking¶

প্রথম সরল চিন্তা: প্রতিটা সংখ্যা x ধরে, তারপর x+1, x+2, ... array-তে আছে কি না বারবার খুঁজে ধারা বাড়াও।

প্রতিটা x-র জন্য:
    length = 1
    যতক্ষণ x+length array-তে আছে (linear search):
        length += 1
    longest update করো

10. Why brute force is slow¶

দুই দিকে খরচ। প্রথমত, "x+length array-তে আছে?" linear search হলে প্রতিটা check O(n) — পুরোটা O(n^3) পর্যন্ত যেতে পারে। দ্বিতীয়ত, এমনকি set ব্যবহার করলেও, যদি প্রতিটা সংখ্যা থেকে ধারা গোনা শুরু করো, একটা লম্বা ধারা বারবার (মাঝখান থেকে) গোনা হয় — কাজ O(n^2)। আসল অপচয়: একই ধারা বহুবার গোনা।

11. Key observation¶

মূল observation: প্রতিটা ধারার একটাই স্বাভাবিক শুরু — যে x-এর জন্য x-1 অনুপস্থিত। কেবল সেই শুরু থেকে গুনলে প্রতিটা সংখ্যা ভেতরের while loop-এ ঠিক একবারই ছোঁয়া হয়। তাই বাইরের loop + ভেতরের while মিলিয়েও মোট কাজ O(n)।

12. Optimized intuition¶

সব সংখ্যা একটা set-এ ভরো (distinct + O(1) lookup)। এবার set-এর প্রতিটা x-এ দেখো x-1 set-এ আছে কি না। না থাকলে x একটা run-শুরু — x+1, x+2, ... যতক্ষণ set-এ আছে গুনে দৈর্ঘ্য বের করো, longest update করো। থাকলে skip (ও পরে অন্য কারও ধারার অংশ হিসেবে গোনা হবে)। মোট O(n)।

13. Thinking tweak¶

মোচড়: sort না করেও ক্রমের প্রশ্নের উত্তর দেওয়া যায় — set + "শুধু শুরু থেকে গোনো" নিয়মে। Seen-set এমনিতে duplicate ধরে; এখানে সেই set-কে দিয়ে "পরের সংখ্যা আছে?" জিজ্ঞেস করিয়ে O(n)-এ structure আবিষ্কার করা হচ্ছে। smart-start নিয়মটাই double-counting ঠেকায়।

14. Step-by-step dry run¶

Input nums = [1, 2, 0, 1]:

num_set = {0, 1, 2} (দ্বিতীয় 1 মিশে গেল)।
x = 0: -1 set-এ নেই → শুরু। 1 আছে, 2 আছে, 3 নেই → length 3 → longest = 3।
x = 1: 0 set-এ আছে → শুরু নয়, skip।
x = 2: 1 set-এ আছে → skip।
উত্তর: 3।

15. Python solution¶

def longest_consecutive(nums):
    num_set = set(nums)                # O(1) membership
    longest = 0
    for x in num_set:
        if x - 1 not in num_set:       # x একটা run-এর শুরু
            length = 1
            while x + length in num_set:
                length += 1
            longest = max(longest, length)
    return longest

# ---- tests ----
assert longest_consecutive([100, 4, 200, 1, 3, 2]) == 4
assert longest_consecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1]) == 9
assert longest_consecutive([]) == 0
assert longest_consecutive([1]) == 1
assert longest_consecutive([1, 2, 0, 1]) == 3
print("সব test pass!")

16. Line-by-line code explanation¶

num_set = set(nums) — distinct value + O(1) membership; পুনরাবৃত্তি এখানেই মুছে যায়।
longest = 0 — খালি input-এও সঠিক উত্তর (0) দেওয়ার জন্য।
for x in num_set — distinct value-গুলোর উপর হাঁটি।
if x - 1 not in num_set — smart start: কেবল run-শুরু থেকে গুনি।
while x + length in num_set: length += 1 — ধারা যতদূর যায় এগোই।
longest = max(longest, length) — সবচেয়ে লম্বা ধারা মনে রাখি।

17. Output walkthrough¶

[100,4,200,1,3,2]-এ একমাত্র run-শুরু 1 (0 নেই) থেকে 1,2,3,4 গোনা হয় → 4; 100 আর 200 আলাদা একক ধারা (length 1)। [0..8] shuffled-এ run-শুরু 0 থেকে 9 গোনা হয় → 9। []-এ loop চলে না → 0। [1,2,0,1]-এ run-শুরু 0 থেকে 0,1,2 → 3। শেষে print: সব test pass!।

18. Time complexity¶

O(n) — set বানানো O(n); বাইরের loop distinct value-র উপর, আর ভেতরের while-এ প্রতিটা সংখ্যা সারা জীবনে একবারই ছোঁয়া হয় (কারণ গোনা শুরু হয় শুধু run-শুরু থেকে), তাই সব মিলিয়ে O(n)।

19. Space complexity¶

O(n) — সব distinct value set-এ জমা থাকে।

20. Common mistakes¶

smart-start শর্ত (x-1 not in set) বাদ দেওয়া — তখন প্রতিটা সংখ্যা থেকে গোনা হয়, কাজ O(n^2) হয়ে যায়।
set না বানিয়ে list-এ in চালানো — প্রতিটা membership O(n), পুরোটা ভয়ংকর ধীর।
duplicate-কে আলাদা গোনা — set ব্যবহার না করলে পুনরাবৃত্তি ভুলভাবে দৈর্ঘ্য বাড়াতে পারে।

21. Which basic problem this inherits from¶

ভিত্তি: Contains Duplicate (#2)-এর seen-set ও O(1) membership। নতুন সংযোজন smart-start নিয়ম, যা প্রতিটা run একবার গুনে O(n) নিশ্চিত করে। সম্পূর্ণ চাল ../patterns.md-র Pattern 4-এ।

22. Similar harder problems¶

Contains Duplicate — https://leetcode.com/problems/contains-duplicate/ (এই tracker-এর #2; set-thinking-র মূল)
Binary Tree Longest Consecutive Sequence — https://leetcode.com/problems/binary-tree-longest-consecutive-sequence/ (গাছে একই ধারা-ধারণা)
Longest Consecutive Sequence (tree variant) — https://leetcode.com/problems/binary-tree-longest-consecutive-sequence-ii/ (দুই দিকের ধারা)

23. Pattern learned¶

Seen-set + smart start: সব value set-এ ভরে O(1) membership পাও, তারপর কেবল run-শুরু (x-1 অনুপস্থিত) থেকে গুনে double-counting এড়িয়ে O(n)-এ ক্রমের গঠন আবিষ্কার করো।

24. Final summary¶

ভবিষ্যতের আমাকে: "longest consecutive", "O(n)-এ, sort ছাড়া" শুনলেই set + smart-start মনে পড়বে। মূল কৌশল একটাই বাক্য — শুধু সেই সংখ্যা থেকে ধারা গোনো, যার আগেরটা নেই। এই নিয়মই O(n^2)-কে O(n) করে; এটা না থাকলে set-ও বাঁচাতে পারবে না।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।