Problem link ও উৎস
- **Original source:** Classic hash-set membership exercise
- **Platform:** LeetCode —
- **Topic:** array / hash set
- **Difficulty:** Medium
- **Pattern:** set + smart start detection (শুধু streak-এর শুরু থেকে গোনা)
- **Basic idea inherited from:** frequency / set membership — "এই সংখ্যাটা আছে কিনা" O(1)-এ জানা
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা integer array `nums` দেওয়া (এলোমেলো, sort করা নেই)। এমন সবচেয়ে লম্বা ধারা (consecutive run) খুঁজে বের করো যেখানে সংখ্যাগুলো পরপর — যেমন `4, 5, 6, 7`। সেই সবচেয়ে লম্বা ধারার **দৈর্ঘ্য** ফেরত দাও। শর্ত: সমাধান **O(n)** সময়ে হতে হবে (অর্থাৎ sort করা যাবে না, কারণ sort O(n log n))।
```text
nums = [100, 4, 200, 1, 3, 2]
সবচেয়ে লম্বা পরপর ধারা: 1, 2, 3, 4 -> দৈর্ঘ্য 4
```
### Input ও output {#8-example-input-and-output}
```text
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)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একদল লোকের জন্মসাল লেখা কাগজ ছড়ানো। তুমি জানতে চাও সবচেয়ে লম্বা "টানা বছর" কত। প্রতিটা বছর হাতে নিয়ে আগে দেখো — এর ঠিক আগের বছরটা কি আছে? থাকলে এটা শুরু নয়, ছেড়ে দাও। না থাকলে এটাই কোনো ধারার শুরু — তখন পরের, তার পরের বছর খুঁজে খুঁজে যত দূর যাও, সেটাই ওই ধারার দৈর্ঘ্য।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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)-ও এড়ায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা সংখ্যা `x`-কে শুরু ধরে নাও, তারপর `x+1`, `x+2`, ... আছে কিনা array-তে বারবার খুঁজে যত দূর যাও দেখো; সবচেয়ে লম্বাটা রাখো।
```text
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)-এ নামিয়ে দেয়।
### ছবিতে বোঝা {#7-visual-explanation}
`nums = [100, 4, 200, 1, 3, 2]` → set `{1,2,3,4,100,200}`:
```text
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
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `[1, 2, 0, 1]` → set `{0, 1, 2}`:
1. `1`: `0` আছে? হ্যাঁ → শুরু নয়, skip।
2. `2`: `1` আছে? হ্যাঁ → skip।
3. `0`: `-1` আছে? না → শুরু। `1`? হ্যাঁ → `2`? হ্যাঁ → `3`? না → `length = 3`; `best = 3`।
4. (দ্বিতীয় `1` set-এ duplicate, আলাদা entry নেই) → loop শেষ। ফল: `3`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
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-এর দৈর্ঘ্য।
### Output মিলিয়ে দেখা {#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!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
JS-এর `Set` দিয়ে O(1) membership, আর শুধু run-এর শুরু থেকে গোনা।
```javascript
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²)-এ ফিরে যায়।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
function longestConsecutive(nums: number[]): number {
const numSet: Set