Problem link ও উৎস
- **Original source:** Classic seen-set / smart-start exercise
- **Platform:** LeetCode —
- **Topic:** hash set
- **Difficulty:** Medium
- **Pattern:** seen-set + smart start
- **Basic idea inherited from:** Contains Duplicate — set-এ ভরে O(1) membership
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা সংখ্যার array `nums` দেওয়া আছে (সাজানো নয়, পুনরাবৃত্তি থাকতে পারে)। এমন **পরপর পূর্ণসংখ্যার (consecutive) সবচেয়ে লম্বা ধারা**-র দৈর্ঘ্য বের করতে হবে — তবে শর্ত: পুরো কাজ **O(n)** সময়ে, অর্থাৎ sort করা যাবে না (sort O(n log n))।
```text
nums = [100, 4, 200, 1, 3, 2]
পরপর ধারা: 1, 2, 3, 4 → দৈর্ঘ্য 4
উত্তর: 4
```
### Input ও output {#8-example-input-and-output}
```text
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; পুনরাবৃত্তি গোনায় আসে না)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা ঘরে অনেকজন, প্রত্যেকের গায়ে একটা নম্বর। তুমি সবচেয়ে লম্বা "পরপর নম্বরের সারি" বানাতে চাও। সবাইকে বারবার জিজ্ঞেস না করে নিয়ম করো: শুধু সেই-ই সারি শুরু করবে, যার ঠিক এক-কম নম্বরওয়ালা কেউ ঘরে নেই (সে-ই স্বাভাবিক "নেতা")। নেতা তারপর এক-বেশি, আরও এক-বেশি ডাকতে থাকে যতক্ষণ পায়। প্রতিটা সারির একজনই নেতা, তাই কেউ দুবার গোনা হয় না।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা **seen-set** pattern (Contains Duplicate, #2)-এর উপর দাঁড়ানো। সেখানে শিখেছ সব value একটা set-এ ভরলে "এটা আছে কি?" প্রশ্নের উত্তর O(1)। এখানে সেই set-এর উপর একটা চালাক সংযোজন — *smart start* — যাতে প্রতিটা ধারা ঠিক একবারই গোনা হয়। [../patterns.md](../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)-এর একমাত্র সহজ পথ।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা সংখ্যা `x` ধরে, তারপর `x+1, x+2, ...` array-তে আছে কি না বারবার খুঁজে ধারা বাড়াও।
```text
প্রতিটা 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 ঠেকায়।
### ছবিতে বোঝা {#7-visual-explanation}
`nums = [100, 4, 200, 1, 3, 2]` → `num_set = {1,2,3,4,100,200}`। শুধু run-শুরু থেকে গুনি:
```text
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
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `nums = [1, 2, 0, 1]`:
1. `num_set = {0, 1, 2}` (দ্বিতীয় `1` মিশে গেল)।
2. `x = 0`: `-1` set-এ নেই → শুরু। `1` আছে, `2` আছে, `3` নেই → length 3 → `longest = 3`।
3. `x = 1`: `0` set-এ আছে → শুরু নয়, skip।
4. `x = 2`: `1` set-এ আছে → skip।
5. উত্তর: `3`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
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)` — সবচেয়ে লম্বা ধারা মনে রাখি।
### Output মিলিয়ে দেখা {#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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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 ব্যবহার না করলে পুনরাবৃত্তি ভুলভাবে দৈর্ঘ্য বাড়াতে পারে।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: Contains Duplicate (#2)-এর seen-set ও O(1) membership। নতুন সংযোজন smart-start নিয়ম, যা প্রতিটা run একবার গুনে O(n) নিশ্চিত করে। সম্পূর্ণ চাল [../patterns.md](../patterns.md)-র Pattern 4-এ।
### পরের অনুশীলন {#22-similar-harder-problems}
- Contains Duplicate —