007 — Longest Consecutive Sequence¶

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

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) সমাধান।

প্রশ্ন ও উদাহরণ¶

সহজ করে প্রশ্ন¶

তোমাকে কতগুলো 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

Input ও 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

চেনা উদাহরণে বোঝা¶

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

ভিত্তির ধারণা¶

আগের কোন ধারণাটি লাগবে¶

এই 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)।

ভেতরের যুক্তি¶

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

কী দিয়ে তথ্য রাখব¶

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

এটি কেন উপযুক্ত¶

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

ধাপে ধাপে সমাধান¶

প্রথম সরল উপায়¶

প্রথম সরল চিন্তা: প্রতিটা সংখ্যা থেকে শুরু করে 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)

কোথায় বেশি কাজ হচ্ছে¶

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

যে বিষয়টি খেয়াল করতে হবে¶

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

আরও কম কাজে সমাধান¶

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

ভাবনার পরিবর্তন¶

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

ছবিতে বোঝা¶

[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

ছোট input-এ ধাপে ধাপে¶

Input [2, 1, 3]:

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

কোড ও ব্যাখ্যা¶

Python¶

Python

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!")

কোডের প্রতিটি অংশ¶

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 থেকেই যায়, তাই সঠিক।

Output মিলিয়ে দেখা¶

[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!।

খরচ ও সাধারণ ভুল¶

সময়¶

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

অতিরিক্ত জায়গা¶

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

যে ভুলগুলো এড়াতে হবে¶

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

শেখা ও পরের অনুশীলন¶

ভিত্তির সঙ্গে সম্পর্ক¶

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

পরের অনুশীলন¶

Longest Consecutive Sequence-এর union-find রূপ — https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/
Binary Tree Longest Consecutive Sequence — https://leetcode.com/problems/binary-tree-longest-consecutive-sequence/
Longest Harmonious Subsequence (count-ভিত্তিক আত্মীয়) — https://leetcode.com/problems/longest-harmonious-subsequence/

কৌশলটি মনে রাখুন¶

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

নিজেকে যাচাই করুন¶

ভবিষ্যতের আমাকে: "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।