Skip to content

007 — Longest Consecutive Sequence

Source

  • Original source: Classic capstone interview problem (hash set with run-start detection)
  • Platform: LeetCode — https://leetcode.com/problems/longest-consecutive-sequence/
  • Topic: hashing + arrays
  • Difficulty: Medium
  • Pattern: Hash set + run starts (only count from a number that has no left neighbor)
  • Basic idea inherited from: এটা একটা cross-topic capstone — এখানে মেশে 05 hashing (সব সংখ্যা একটা set-এ রেখে O(1)-এ "x আছে কি?" জিজ্ঞেস করা) আর 02 arrays (একটা সংখ্যা থেকে শুরু করে x, x+1, x+2 ... রৈখিক ভাবে একটা run বাড়িয়ে যাওয়া)। দুই tool জোড়া লাগলেই O(n) সমাধান।

1. Problem in simple words

তোমাকে কতগুলো integer-এর একটা array দেওয়া (এলোমেলো, sorted না, duplicate থাকতে পারে)। তোমার কাজ: এমন একটা সবচেয়ে লম্বা টুকরো বের করো যেখানে সংখ্যাগুলো পরপর (consecutive, যেমন 1,2,3,4) — কিন্তু array-তে তারা পাশাপাশি থাকার দরকার নেই, যেকোনো জায়গায় ছড়িয়ে থাকলেও চলবে। সেই সবচেয়ে লম্বা run-এর দৈর্ঘ্য return করো। শর্ত: O(n) সময়ে করতে হবে।

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

2. Which basic idea does this inherit from?

এই problem দুটো আগের chapter-এর tool জোড়া দেয়:

  • 05 hashing থেকে: সব সংখ্যা একটা set-এ ঢালা, যাতে "x+1 কি আছে?" — এই প্রশ্নের উত্তর গড়ে O(1)-এ পাওয়া যায়।
  • 02 arrays থেকে: একটা সংখ্যা থেকে শুরু করে x, x+1, x+2, ... ধরে রৈখিক ভাবে একটা run-এর দৈর্ঘ্য গোনা।

একা hashing দেয় তাৎক্ষণিক membership-প্রশ্ন; একা array-walk দেয় run বাড়ানোর কৌশল। দুটো মিললে sort না করেই O(n)।

3. What is the hidden math or logic?

লুকানো logic একটা run-start filter: একটা সংখ্যা x কোনো consecutive run-এর শুরু ঠিক তখনই যখন x-1 set-এ নেই। শুধু এমন start থেকেই run গুনলে, প্রতিটা সংখ্যা পুরো algorithm-এ সর্বোচ্চ দু'বার ছোঁয়া হয় (একবার start-চেক, একবার কোনো একটা run-এর ভেতরে) — এজন্যই মোট কাজ O(n), nested দেখতে হলেও।

4. Which data structure is needed?

একটা hash set (Python-এ set)। এটা একই সাথে duplicate মুছে দেয় আর "x+1 কি আছে?" / "x-1 কি আছে?" প্রশ্নের O(1) উত্তর দেয় — 05 hashing-এর মূল শক্তি।

5. Why this data structure fits

run বাড়াতে আমাদের বারবার জিজ্ঞেস করতে হয় "পরের সংখ্যাটা কি কোথাও আছে?"। array বা list-এ এই খোঁজ O(n), তাই পুরোটা O(n^2) হয়ে যেত। hash set সেই খোঁজকে O(1) করে দেয়, তাই run-extension সস্তা। আবার set আপনাআপনি duplicate ফেলে দেয়, তাই গোনায় ভুল হয় না। এজন্যই hashing (05) + array-walk (02) এখানে নিখুঁত।

6. Real-life analogy

ভাবো একগাদা এলোমেলো বাড়ির নম্বরওয়ালা চিঠি তোমার হাতে। তুমি দ্রুত দেখতে চাও সবচেয়ে লম্বা কোন রাস্তার পরপর বাড়িগুলোর চিঠি আছে। বুদ্ধি: শুধু সেই বাড়ি থেকে গোনা শুরু করো যার ঠিক আগের নম্বরের চিঠি তোমার কাছে নেই (মানে সেটাই রাস্তার শুরু) — তারপর পরের, তার পরের নম্বর আছে কি না দেখতে দেখতে এগোও। মাঝখান থেকে শুরু করলে একই রাস্তা বারবার গোনা হয়।

7. Visual explanation

[100, 4, 200, 1, 3, 2] → set, তারপর শুধু run-start থেকে গোনা:

set = {1, 2, 3, 4, 100, 200}

x=1   : 0 নেই -> START; 1,2,3,4 আছে -> length 4   <- সবচেয়ে বড়
x=2   : 1 আছে -> start না, skip
x=3   : 2 আছে -> skip
x=4   : 3 আছে -> skip
x=100 : 99 নেই -> START; 101 নেই -> length 1
x=200 : 199 নেই -> START; 201 নেই -> length 1

উত্তর = 4

8. Example input and output

Input : [100, 4, 200, 1, 3, 2]
Output: 4                                   # 1,2,3,4

Edge case 1 (খালি): Input: []              -> Output: 0
Edge case 2 (ডুপ্লিকেট): Input: [1,2,2,3]  -> Output: 3   # 1,2,3 (ডুপ্লিকেট গোনে না)
Edge case 3 (সব আলাদা): Input: [10, 30, 20] -> Output: 1

9. Brute force thinking

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

best = 0
for x in nums:
    length = 1
    while (x + length) in nums:   # nums একটা list হলে এই খোঁজ O(n)
        length += 1
    best = max(best, length)

10. Why brute force is slow

দুটো সমস্যা: (1) in nums যদি list-এ চলে, প্রতিটা খোঁজ O(n), তাই পুরোটা O(n^3); (2) এমনকি set ব্যবহার করলেও, প্রতিটা সংখ্যা থেকে run গুনলে একই run বহুবার গোনা হয় (1 থেকে গুনলাম, আবার 2 থেকেও গুনলাম)। এই দ্বিতীয় অপচয়ই run-start filter (নিচে) দূর করে।

11. Key observation

মূল observation: একটা run শুধু তার শুরু থেকে একবার গুনলেই যথেষ্ট — আর x শুরু ঠিক তখনই যখন x-1 set-এ নেই। এই filter দেওয়ায় প্রতিটা সংখ্যা সব মিলিয়ে সর্বোচ্চ দু'বার ছোঁয়া হয়, তাই sort ছাড়াই পুরো কাজ O(n)।

12. Optimized intuition

সব সংখ্যা একটা set-এ ঢালো (duplicate মুছে যায়, O(1) lookup পাও)। প্রতিটা সংখ্যা x-এর জন্য দেখো x-1 set-এ আছে কি না — থাকলে এটা কোনো run-এর মাঝখানে, skip করো। না থাকলে এটাই run-এর শুরু: x, x+1, x+2, ... যতক্ষণ set-এ পাও, দৈর্ঘ্য গোনো। সবচেয়ে বড় দৈর্ঘ্যটাই উত্তর।

13. Thinking tweak

মোচড়: "sort করে পাশাপাশি consecutive খুঁজব" (O(n log n)) ভাবার বদলে ভাবো "set-এ ফেলে শুধু run-start থেকে সামনে গুনব।" sort-এর দরকার মুছে যায়, প্রতিটা সংখ্যা সর্বোচ্চ দু'বার ছোঁয়া হয় — O(n)।

14. Step-by-step dry run

Input [2, 1, 3]:

  1. set = {1, 2, 3}, best = 0
  2. x = 2: 1 আছে → start না, skip
  3. x = 1: 0 নেই → START; 2 আছে (len 2), 3 আছে (len 3), 4 নেই → থামো; best = 3
  4. x = 3: 2 আছে → skip
  5. শেষ → return best = 3

15. Python solution

def longest_consecutive(nums):
    num_set = set(nums)            # ডুপ্লিকেট মুছে যায়, O(1) lookup
    best = 0
    for x in num_set:
        if x - 1 in num_set:       # x run-এর শুরু না -> skip
            continue
        length = 1                 # x একটা run-এর শুরু
        while x + 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                     # খালি
assert longest_consecutive([1, 2, 2, 3]) == 3           # ডুপ্লিকেট গোনে না
assert longest_consecutive([10, 30, 20]) == 1           # সব আলাদা
assert longest_consecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1]) == 9  # 0..8
assert longest_consecutive([-2, -1, 0, 1]) == 4         # negative সহ
print("সব test pass!")

16. Line-by-line code explanation

  • num_set = set(nums) — array-কে set-এ রূপান্তর: duplicate উবে যায়, lookup O(1) হয় (05 hashing)।
  • for x in num_set — প্রতিটা স্বতন্ত্র সংখ্যা একবার দেখি।
  • if x - 1 in num_set: continue — x-এর বাঁ-প্রতিবেশী থাকলে এটা শুরু না; এই filter-ই O(n) নিশ্চিত করে।
  • length = 1 ... while x + length in num_set — শুরু থেকে ডান দিকে যতদূর পরপর সংখ্যা আছে, গুনে যাই (02 array-walk)।
  • best = max(best, length) — সবচেয়ে লম্বা run ধরে রাখি।
  • return best — খালি input-এ best 0 থেকেই যায়, তাই সঠিক।

17. Output walkthrough

[100,4,200,1,3,2] → set {1,2,3,4,100,200}। শুধু 1, 100, 200 start (তাদের বাঁ-প্রতিবেশী নেই); 1 থেকে run 1,2,3,4 দৈর্ঘ্য 4, বাকি দুটো দৈর্ঘ্য 1। best = 4 — assert pass। ডুপ্লিকেট, খালি, negative case-ও সঠিক। শেষে print: সব test pass!।

18. Time complexity

O(n) — set বানানো O(n); প্রতিটা সংখ্যা start-চেকে একবার, আর সর্বোচ্চ একটা run-এর ভেতরে একবার ছোঁয়া হয়, তাই inner while থাকা সত্ত্বেও মোট রৈখিক।

19. Space complexity

O(n) — সব স্বতন্ত্র সংখ্যা set-এ জমা থাকে।

20. Common mistakes

  • run-start filter বাদ দেওয়া (প্রতি সংখ্যা থেকেই গোনা) — তখন একই run বহুবার গোনা হয়ে O(n^2)-এর দিকে চলে যায়।
  • nums (list) সরাসরি in দিয়ে খোঁজা — O(n) lookup, পুরো লাভ নষ্ট; আগে set বানাও।
  • duplicate handle না করা — list-এ গুনলে ভুল হয়, কিন্তু set আপনাআপনি সেটা সারায়।
  • খালি input ভুলে যাওয়া — এখানে best = 0 শুরু করায় এমনিতেই ঠিক, তবু মুখে বলা ভালো।

21. Which basic problem this inherits from

ভিত্তি: hash set membership (05 hashing, ../../05-hashing/) + একটা মান থেকে সামনে রৈখিক run গোনা (02 arrays, ../../02-arrays-and-strings/)। "Two Sum"-এর মতোই এখানে set/dict দিয়ে O(n) lookup-ই মূল চাল।

22. Similar harder problems

23. Pattern learned

Hash set + run starts: সব মান set-এ ফেলে O(1) lookup পাও, তারপর শুধু "যার বাঁ-প্রতিবেশী নেই" এমন run-start থেকে সামনে গুনে O(n)-এ সবচেয়ে লম্বা consecutive run বের করা — sort এড়ানোর ক্লাসিক চাল।

24. Final summary

ভবিষ্যতের আমাকে: "consecutive / পরপর সংখ্যা, sorted না, O(n) চাই" শুনলেই hash set + run-start filter মনে করবে। মূল চাবি — শুধু run-এর শুরু (x-1 নেই) থেকে গোনা, এতেই nested while থাকা সত্ত্বেও মোট O(n) থাকে। sort করতে গেলে O(n log n), এটাই এড়ানোর জায়গা।

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