Problem link ও উৎস
- **Original source:** Classic capstone interview problem (hash set with run-start detection)
- **Platform:** LeetCode —
- **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) সমাধান।
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে কতগুলো integer-এর একটা array দেওয়া (এলোমেলো, sorted না, duplicate থাকতে পারে)। তোমার কাজ: এমন একটা সবচেয়ে লম্বা টুকরো বের করো যেখানে সংখ্যাগুলো **পরপর** (consecutive, যেমন `1,2,3,4`) — কিন্তু array-তে তারা পাশাপাশি থাকার দরকার নেই, যেকোনো জায়গায় ছড়িয়ে থাকলেও চলবে। সেই সবচেয়ে লম্বা run-এর **দৈর্ঘ্য** return করো। শর্ত: O(n) সময়ে করতে হবে।
```text
array : [100, 4, 200, 1, 3, 2]
সবচেয়ে লম্বা run : [1, 2, 3, 4] -> দৈর্ঘ্য = 4
```
### Input ও output {#8-example-input-and-output}
```text
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
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একগাদা এলোমেলো বাড়ির নম্বরওয়ালা চিঠি তোমার হাতে। তুমি দ্রুত দেখতে চাও সবচেয়ে লম্বা কোন রাস্তার পরপর বাড়িগুলোর চিঠি আছে। বুদ্ধি: শুধু সেই বাড়ি থেকে গোনা শুরু করো যার **ঠিক আগের নম্বরের** চিঠি তোমার কাছে নেই (মানে সেটাই রাস্তার শুরু) — তারপর পরের, তার পরের নম্বর আছে কি না দেখতে দেখতে এগোও। মাঝখান থেকে শুরু করলে একই রাস্তা বারবার গোনা হয়।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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) এখানে নিখুঁত।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা সংখ্যা থেকে শুরু করে `x+1, x+2, ...` array-তে আছে কি না খুঁজে run-এর দৈর্ঘ্য বের করো; সবচেয়ে বড়টা রাখো।
```text
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)।
### ছবিতে বোঝা {#7-visual-explanation}
`[100, 4, 200, 1, 3, 2]` → set, তারপর শুধু run-start থেকে গোনা:
```text
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-এ ধাপে ধাপে {#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`
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```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!")
```
### কোডের প্রতিটি অংশ {#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 থেকেই যায়, তাই সঠিক।
### Output মিলিয়ে দেখা {#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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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` শুরু করায় এমনিতেই ঠিক, তবু মুখে বলা ভালো।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: hash set membership (05 hashing, [../../05-hashing/](../../05-hashing/README.md)) + একটা মান থেকে সামনে রৈখিক run গোনা (02 arrays, [../../02-arrays-and-strings/](../../02-arrays-and-strings/README.md))। "Two Sum"-এর মতোই এখানে set/dict দিয়ে O(n) lookup-ই মূল চাল।
### পরের অনুশীলন {#22-similar-harder-problems}
- Longest Consecutive Sequence-এর union-find রূপ —