018 — Longest Consecutive Sequence¶

Source¶

Original source: Classic hash-set membership exercise
Platform: LeetCode — https://leetcode.com/problems/longest-consecutive-sequence/
Topic: array / hash set
Difficulty: Medium
Pattern: set + smart start detection (শুধু streak-এর শুরু থেকে গোনা)
Basic idea inherited from: frequency / set membership — "এই সংখ্যাটা আছে কিনা" O(1)-এ জানা

1. Problem in simple words¶

একটা integer array nums দেওয়া (এলোমেলো, sort করা নেই)। এমন সবচেয়ে লম্বা ধারা (consecutive run) খুঁজে বের করো যেখানে সংখ্যাগুলো পরপর — যেমন 4, 5, 6, 7। সেই সবচেয়ে লম্বা ধারার দৈর্ঘ্য ফেরত দাও। শর্ত: সমাধান O(n) সময়ে হতে হবে (অর্থাৎ sort করা যাবে না, কারণ sort O(n log n))।

nums = [100, 4, 200, 1, 3, 2]
সবচেয়ে লম্বা পরপর ধারা: 1, 2, 3, 4  ->  দৈর্ঘ্য 4

2. Which basic idea does this inherit from?¶

ভিত হলো set membership — একটা hash set-এ "x আছে কিনা" average O(1)-এ জানা (problem 2 Two Sum-এর "আগে দেখেছি কিনা"-র জ্ঞাতি)। sort না করেই কোন সংখ্যার ঠিক পরের/আগের সংখ্যা set-এ আছে কিনা সাথে সাথে দেখা যায় — এটাই পুরো trick-এর মেরুদণ্ড।

3. What is the hidden math or logic?¶

লুকানো logic: প্রতিটা consecutive run-এর একটা অনন্য শুরু আছে — সেই সংখ্যা x যার ঠিক আগের সংখ্যা x-1 set-এ নেই। তাই run প্রতি ঠিক একবার কাজ শুরু হয়। এই "শুধু শুরু থেকে গোনা" নিয়মের জন্যই inner while-এর মোট কাজ সব run মিলিয়ে O(n) — প্রতিটা সংখ্যা ঠিক একবার (তার নিজের run গোনার সময়) ছোঁয়া হয়।

4. Which data structure is needed?¶

একটা hash set — সব সংখ্যা ভরে রাখি। সাথে দুটো integer: চলতি run-এর length আর এ যাবৎ সেরা best। (set ব্যবহারে duplicate আপনাআপনি বাদ পড়ে।)

5. Why this data structure fits¶

কাজটার মূল প্রশ্ন: "x-1 কি আছে?" আর "x+1 কি আছে?" — দুটোই membership query। set এই lookup average O(1)-এ দেয়। array-তে এই প্রশ্নের উত্তর প্রতিবার O(n) search লাগত (মোট O(n^2))। set সেটাকে O(n)-এ নামায়, আর sort-এর O(n log n)-ও এড়ায়।

6. Real-life analogy¶

ভাবো একদল লোকের জন্মসাল লেখা কাগজ ছড়ানো। তুমি জানতে চাও সবচেয়ে লম্বা "টানা বছর" কত। প্রতিটা বছর হাতে নিয়ে আগে দেখো — এর ঠিক আগের বছরটা কি আছে? থাকলে এটা শুরু নয়, ছেড়ে দাও। না থাকলে এটাই কোনো ধারার শুরু — তখন পরের, তার পরের বছর খুঁজে খুঁজে যত দূর যাও, সেটাই ওই ধারার দৈর্ঘ্য।

7. Visual explanation¶

nums = [100, 4, 200, 1, 3, 2] → set {1,2,3,4,100,200}:

100: আগে 99 আছে? না -> শুরু। 101 আছে? না -> length 1
4  : আগে 3 আছে? হ্যাঁ -> শুরু নয়, skip
200: আগে 199 আছে? না -> শুরু। 201? না -> length 1
1  : আগে 0 আছে? না -> শুরু। 2? হ্যাঁ ->3? হ্যাঁ ->4? হ্যাঁ ->5? না -> length 4  ✅
3  : আগে 2 আছে? হ্যাঁ -> skip
2  : আগে 1 আছে? হ্যাঁ -> skip

best = 4

8. Example input and output¶

Input : [100, 4, 200, 1, 3, 2]          -> 4   (1,2,3,4)
Input : [0,3,7,2,5,8,4,6,0,1]           -> 9   (0..8)

Edge case 1 (খালি):        []           -> 0
Edge case 2 (duplicate):   [1, 2, 0, 1] -> 3   (0,1,2)

9. Brute force thinking¶

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

best = 0
for x in nums:
    length = 1
    while (x + length) in nums:   # array-তে খোঁজা = O(n)
        length += 1
    best = max(best, length)

10. Why brute force is slow¶

(x + length) in nums array-র উপর হলে প্রতিবার O(n), আর সেটা প্রতিটা সংখ্যার জন্য — মোট O(n^2) বা তারও খারাপ। উপরন্তু কোনো সংখ্যা কোন run-এর শুরু সেটা না দেখায় একই run বারবার পুরোটা গোনা হয়। sort করলে O(n log n) হতো, কিন্তু problem চায় কড়া O(n)।

11. Key observation¶

দুটো observation মিলে magic: (১) lookup-কে set দিয়ে O(1) করো; (২) শুধু সেই সংখ্যা থেকে গোনা শুরু করো যার x-1 set-এ নেই (অর্থাৎ run-এর শুরু)। এই দুইয়ে inner loop-এর মোট iteration সব run মিলিয়ে n-এর বেশি হয় না — প্রতিটা সংখ্যা ঠিক একবার গোনা হয়।

12. Optimized intuition¶

সব সংখ্যা একটা set-এ ভরো। প্রতিটা সংখ্যা x নিয়ে দেখো x-1 set-এ আছে কিনা — থাকলে এটা কোনো run-এর মাঝখানে, skip। না থাকলে এটাই শুরু: x+1, x+2, ... যতক্ষণ set-এ আছে গুনতে থাকো, সেই length দিয়ে best update করো। যেহেতু গোনা শুধু run-এর শুরু থেকেই হয়, মোট কাজ O(n)।

13. Thinking tweak¶

মোচড়: "ধারা খুঁজতে আগে sort করতেই হবে" ধারণা ফেলে দাও। বরং ভাবো "প্রতিটা সংখ্যাকে জিজ্ঞেস করি — তুমি কি কোনো ধারার প্রথম? (মানে তোমার আগেরজন নেই?) হলে তোমার থেকে গুনি।" এই "শুধু শুরু থেকে গোনা" শর্তই O(n^2)-কে O(n)-এ নামিয়ে দেয়।

14. Step-by-step dry run¶

Input [1, 2, 0, 1] → set {0, 1, 2}:

1: 0 আছে? হ্যাঁ → শুরু নয়, skip।
2: 1 আছে? হ্যাঁ → skip।
0: -1 আছে? না → শুরু। 1? হ্যাঁ → 2? হ্যাঁ → 3? না → length = 3; best = 3।
(দ্বিতীয় 1 set-এ duplicate, আলাদা entry নেই) → loop শেষ। ফল: 3।

15. Python solution¶

def longest_consecutive(nums):
    num_set = set(nums)                 # O(1) membership; duplicate বাদ
    best = 0
    for n in num_set:
        if n - 1 not in num_set:        # n একটা run-এর শুরু
            length = 1
            while n + length in num_set:
                length += 1             # পরের সংখ্যা থাকলে run বাড়াও
            best = max(best, length)
    return best

# ---- 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, 2, 0, 1]) == 3       # duplicate-সহ
print("সব test pass!")

16. Line-by-line code explanation¶

num_set = set(nums) — O(1) membership-এর জন্য; একই সাথে duplicate মুছে যায়।
for n in num_set — প্রতিটা আলাদা সংখ্যা একবার দেখি।
if n - 1 not in num_set — n-এর আগেরজন নেই মানে n কোনো run-এর শুরু; এই গার্ডই মাঝের সংখ্যা থেকে গোনা ঠেকায়।
while n + length in num_set: length += 1 — শুরু থেকে পরপর সংখ্যা যতক্ষণ আছে, run বাড়াই।
best = max(best, length) — এই run-এর দৈর্ঘ্য দিয়ে সেরা update।
return best — সবচেয়ে লম্বা run-এর দৈর্ঘ্য।

17. Output walkthrough¶

[100,4,200,1,3,2] → 1 থেকে 1,2,3,4 গুনে best=4, বাকিরা হয় শুরু নয় (skip) নয়তো length 1 → 4, assert pass। [0,3,7,2,5,8,4,6,0,1] → 0 থেকে 0..8 = 9; [] → loop চলে না, 0; [1,2,0,1] → 0 থেকে 0,1,2 = 3। শেষে print: সব test pass!।

18. Time complexity¶

O(n) — set বানানো O(n); outer loop প্রতিটা সংখ্যা একবার; inner while শুধু run-এর শুরু থেকে চলে বলে সব run মিলিয়ে মোট inner-step ও O(n) (প্রতিটা সংখ্যা ঠিক একবার গোনা)।

19. Space complexity¶

O(n) — set-এ সব আলাদা সংখ্যা রাখা হয়।

20. Common mistakes¶

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

21. Which basic problem this inherits from¶

ভিত্তি: hash-set membership (Two Sum #2-এর "complement আগে দেখেছি কিনা"-র চাচাতো ভাই) + smart start detection। chapter-এর ../patterns.md-এর "Pattern 5 — Frequency Counting" (hash-এ O(1) lookup)-এর আত্মীয়; এখানে count-এর বদলে শুধু membership কাজে লাগে।

22. Similar harder problems¶

Longest Consecutive Sequence-এর dynamic variant — https://leetcode.com/problems/binary-tree-longest-consecutive-sequence/
Longest Consecutive Sequence II — https://leetcode.com/problems/binary-tree-longest-consecutive-sequence-ii/
Number of Islands (grid-এ connected component গোনা, একই "শুধু শুরু থেকে expand" ভাব) — https://leetcode.com/problems/number-of-islands/

23. Pattern learned¶

Set + smart start: "sort ছাড়া O(n)-তে পরপর/connected অংশ খোঁজো" দেখলে সব কিছু hash set-এ ভরো, তারপর শুধু "শুরু" element থেকে (যার আগেরজন নেই) expand করো — প্রতিটা element একবার ছোঁয়া, O(n)।

24. Final summary¶

ভবিষ্যতের আমাকে: "consecutive run = set-এ ভরো; শুধু সেই সংখ্যা থেকে গোনো যার x-1 নেই।" "O(n)-তে longest consecutive / streak" দেখলেই set membership + start-detection মনে করবে — sort নয়, O(n) time, O(n) space।

25. JavaScript solution (with test cases)¶

JS-এর Set দিয়ে O(1) membership, আর শুধু run-এর শুরু থেকে গোনা।

const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// longest consecutive run length (set + smart start)
function longestConsecutive(nums) {
  const numSet = new Set(nums);        // O(1) membership; duplicate বাদ
  let best = 0;
  for (const n of numSet) {
    if (!numSet.has(n - 1)) {          // n একটা run-এর শুরু
      let length = 1;
      while (numSet.has(n + length)) length++;
      best = Math.max(best, length);
    }
  }
  return best;
}
// ---- test cases (example + edge) ----
assert(longestConsecutive([100, 4, 200, 1, 3, 2]) === 4, "classic");
assert(longestConsecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1]) === 9, "long");
assert(longestConsecutive([]) === 0, "empty");                   // edge
assert(longestConsecutive([1, 2, 0, 1]) === 3, "dup");           // edge
console.log("সব JS test pass!");

JS টীকা: new Set(nums) average O(1) has() দেয় (array-র includes O(n))। for...of দিয়ে Set iterate করা যায়; start-guard !numSet.has(n - 1) ছাড়া complexity O(n²)-এ ফিরে যায়।

26. TypeScript solution (with test cases)¶

function longestConsecutive(nums: number[]): number {
  const numSet: Set<number> = new Set(nums);
  let best = 0;
  for (const n of numSet) {
    if (!numSet.has(n - 1)) {
      let length = 1;
      while (numSet.has(n + length)) length++;
      best = Math.max(best, length);
    }
  }
  return best;
}
function expect<T>(actual: T, exp: T, msg = ""): void {
  if (actual !== exp) throw new Error(`FAIL ${msg}: got ${actual}`);
}
expect(longestConsecutive([100, 4, 200, 1, 3, 2]), 4, "classic");
expect(longestConsecutive([]), 0, "empty");
expect(longestConsecutive([1, 2, 0, 1]), 3, "dup");
console.log("সব TS test pass!");

TS টীকা: Set<number> declare করায় has(n - 1)-এ শুধু number query হয়; ভুল type-এর element ঢোকানো compile-time-এ আটকে যায়, তাই membership logic নিরাপদ।

27. কোথায় কাজে লাগে (real-world use)¶

Streak detection: ব্যবহারকারীর টানা active দিন (consecutive login streak) sort ছাড়াই বের করা।
ID/range gap analysis: এলোমেলো ID set থেকে সবচেয়ে লম্বা continuous block খুঁজে compaction পরিকল্পনা।
Calendar/booking: ছড়ানো slot থেকে সবচেয়ে লম্বা টানা available range।
Genomics: scattered position থেকে দীর্ঘতম contiguous region detect করা।
Network/IP: ব্যবহৃত IP set-এ দীর্ঘতম consecutive free/used block।
Game progression: আনলক করা level থেকে দীর্ঘতম টানা সম্পূর্ণ ধারা।

মূল pattern: সব hash set-এ ভরো, শুধু "শুরু" (যার আগেরজন নেই) থেকে expand করো — sort ছাড়াই O(n)।

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