Problem link ও উৎস
- **Original source:** LeetCode — Jump Game
- **Platform:** LeetCode —
- **Topic:** Greedy math tricks → furthest reachable index track করা
- **Difficulty:** Medium
- **Pattern:** furthest reach (এক pass-এ "সর্বোচ্চ কোথায় পৌঁছাই" track)
- **Basic idea inherited from:** — (এই level-এর প্রথম "এক সংখ্যা track" greedy)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা array `nums` দেওয়া আছে। তুমি শুরুতে index 0-তে দাঁড়িয়ে। প্রতিটা ঘরে লেখা সংখ্যা বলে দেয় **সেখান থেকে তুমি সর্বোচ্চ কত ঘর সামনে লাফাতে পারো**। যেমন `nums[i] = 3` মানে i থেকে তুমি 1, 2 বা 3 ঘর সামনে যেতে পারো।
প্রশ্ন: তুমি কি **শেষ ঘরে (last index)** পৌঁছাতে পারবে? শুধু হ্যাঁ/না বলো।
উদাহরণ: `[2, 3, 1, 1, 4]` → হ্যাঁ; `[3, 2, 1, 0, 4]` → না (একটা 0-তে আটকে যাবে)।
### Input ও output {#6-example-input-and-output}
```text
nums -> output (ব্যাখ্যা)
-----------------------------------------------------
[2, 3, 1, 1, 4] -> True (0→1→4, বা 0→2→...→4)
[3, 2, 1, 0, 4] -> False (index 3-এর 0-তে আটকে)
[0] -> True (একটাই ঘর, শুরুতেই শেষে আছি)
[0, 1] -> False (প্রথম ঘরেই 0, নড়াই যায় না)
[2, 0, 0] -> True (0 থেকে এক লাফে 2 পর্যন্ত)
```
খেয়াল করো — `[0]` হলো True (একটা ঘর মানেই গন্তব্যে আছি), কিন্তু `[0, 1]` False (নড়তেই পারছ না)। এই edge case গুলো ধরা জরুরি।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো তুমি নদীর পাথর টপকে ওপারে যাচ্ছ। প্রতিটা পাথরে দাঁড়িয়ে তুমি দেখতে পাও **সামনে সর্বোচ্চ কোন পাথর পর্যন্ত এক লাফে যাওয়া সম্ভব**।
তোমার মাথায় শুধু একটা সংখ্যা রাখলেই চলে — "আমি এ পর্যন্ত যা দেখেছি, তাতে সবচেয়ে দূরের কোন পাথর পর্যন্ত পৌঁছানো সম্ভব?" কোন পাথর থেকে কোন লাফ দিলে সেখানে গেলাম — সেই ইতিহাস মনে রাখার দরকার নেই। যদি হাঁটতে হাঁটতে এমন এক পাথরে পৌঁছাও যেটা তোমার "সর্বোচ্চ পৌঁছানো সম্ভব" সীমার বাইরে, তাহলে বুঝবে — এখানে তো আসাই যেত না, ওপার অসম্ভব।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
এটা greedy level-এর প্রথম "এক pass-এ একটা সংখ্যা track" ধরনের problem, তাই আগের কোনো greedy-র উপর সরাসরি দাঁড়ায় না (`inherited from: —`)।
তবে এর পেছনে আছে level 0-এর সেই অভ্যাস — array-র উপর এক loop চালিয়ে চলন্ত একটা মান (running max/min) ধরে রাখা (যেমন running maximum বের করা)। এখানে সেই "running max"-ই হয়ে গেছে "furthest reachable index"। আর এই problem নিজেই বীজ — 105 (Gas Station)-এ একই দর্শন ("এক pass, এক সংখ্যা, observation") ফিরে আসবে, তাই tracker-এ 105 এর "inherits from" 104।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea — **reachability হলো একটা একমুখী, monotone সম্পত্তি**। কোন ঘর থেকে লাফালাম সেটা গুরুত্বপূর্ণ নয়; গুরুত্বপূর্ণ শুধু **এখন পর্যন্ত সর্বোচ্চ কোন index পর্যন্ত পৌঁছানো সম্ভব**।
এই এক সংখ্যা (`furthest`) ধরে রাখলেই হয়: কোনো ঘরে দাঁড়িয়ে তুমি `i + nums[i]` পর্যন্ত যেতে পারো, তাই furthest কে বারবার `max(furthest, i + nums[i])` দিয়ে update করো। যদি কখনো এমন একটা index-এ পৌঁছাও যেটা furthest-কেও ছাড়িয়ে গেছে (`i > furthest`), তাহলে ওখানে আসাই অসম্ভব — answer না।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সরাসরি চিন্তা — **সব সম্ভাব্য লাফ চেষ্টা করো**। কোনো ঘর থেকে 1 থেকে `nums[i]` পর্যন্ত প্রতিটা লাফ দিয়ে দেখো, recursion-এ এগোও; কোনো একটা path শেষ ঘরে পৌঁছালেই True:
```python
def can_jump_brute(nums):
n = len(nums)
def reach(i):
if i >= n - 1:
return True
for step in range(1, nums[i] + 1):
if reach(i + step):
return True
return False
return reach(0)
```
এটা প্রতিটা সম্ভাবনা ঘেঁটে দেখে, তাই উত্তর সবসময় সঠিক — আমরা একে greedy-র "সত্যের পরিমাপক" হিসেবে ব্যবহার করব।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
এই recursion একই index বারবার বিভিন্ন path থেকে দেখে, তাই গাছটা exponential-ভাবে ফাঁপে। বড় array-তে (বিশেষত যেখানে সংখ্যা বড়) এটা অসহনীয় ধীর।
```text
[2,2,2,2,...,2] টাইপ array-তে প্রতিটা ঘর থেকে 2টা শাখা —
একই ঘর বহুবার আলাদা path-এ পরিদর্শন হয়।
brute force : exponential (ধীর)
greedy : O(n) এক pass — কারণ অপ্রয়োজনীয় তথ্য ("কোন ঘর থেকে এলাম") ফেলে দিই
```
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল observation: **"কোন ঘর থেকে লাফালাম" তথ্যটা দরকারই নেই।** শুধু track করো এখন পর্যন্ত সর্বোচ্চ কোন index reachable (`furthest`)। বাঁ থেকে ডানে এক pass:
```python
def can_jump(nums):
furthest = 0
for i, x in enumerate(nums):
if i > furthest: # এই ঘরেই তো পৌঁছানো যায় না
return False
furthest = max(furthest, i + x)
return True
```
**Greedy choice:** প্রতিটা reachable ঘরে দাঁড়িয়ে furthest-কে যতদূর পারো বাড়িয়ে নাও (`max`)।
**কেন কাজ করে (exchange argument, এক লাইন):** শেষে পৌঁছানো যায় কি না সেটা শুধু "reachable index-এর সেট" দিয়ে ঠিক হয়, আর সেই সেট হলো `[0, furthest]` — একটা একটানা পরিসর; তাই কোনো optimal path-এর প্রতিটা লাফকেই "furthest পর্যন্ত যাওয়া" দিয়ে বদলে দিলেও reachable পরিসর কখনো ছোট হয় না, মানে greedy কোনো reachable ঘর হারায় না।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
এক লাইনের "আহা!":
> "শেষে পৌঁছাতে পারব কিনা — এটা একটা সংখ্যাতেই ধরা: এ পর্যন্ত সবচেয়ে দূরে কোথায় পৌঁছানো সম্ভব।"
পুরো path বা "কোন ঘর থেকে কোথায় লাফালাম" — এসব অপ্রয়োজনীয় তথ্য মাথা থেকে ঝেড়ে ফেলাই tweak। অপ্রয়োজনীয় তথ্য বাদ দেওয়াই এখানে greedy-র আসল শক্তি, আর exponential brute-কে এক pass O(n)-এ নামিয়ে আনে।
### ছবিতে বোঝা {#5-visual-explanation}
`nums = [2, 3, 1, 1, 4]` — প্রতিটা ঘর থেকে কতদূর reach, আর furthest কীভাবে বাড়ে:
```text
index : 0 1 2 3 4
nums : 2 3 1 1 4
\ \
i=0: furthest = max(0, 0+2) = 2 reach: 0..2
i=1: 1 ≤ 2 ✓, furthest = max(2,1+3)=4 reach: 0..4 ← শেষ ছুঁয়ে ফেলল!
i=2: 2 ≤ 4 ✓ i=3: 3 ≤ 4 ✓ i=4: 4 ≤ 4 ✓
শেষ index 4 ≤ furthest 4 → True
```
এবার fail case `nums = [3, 2, 1, 0, 4]`:
```text
index : 0 1 2 3 4
nums : 3 2 1 0 4
i=0: furthest = max(0,0+3)=3
i=1: 1≤3 ✓ furthest=max(3,1+2)=3
i=2: 2≤3 ✓ furthest=max(3,2+1)=3
i=3: 3≤3 ✓ furthest=max(3,3+0)=3 ← 0 ঘরে আটকে গেল, furthest বাড়ল না
i=4: 4 > 3 ✗ → index 4-এ আসাই অসম্ভব → False
```
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`nums = [3, 2, 1, 0, 4]` (fail case) ধীরে চালাই:
| i | nums[i] | i > furthest? | furthest = max(furthest, i+nums[i]) |
| --- | --- | --- | --- |
| 0 | 3 | 0 > 0? না | max(0, 0+3) = 3 |
| 1 | 2 | 1 > 3? না | max(3, 1+2) = 3 |
| 2 | 1 | 2 > 3? না | max(3, 2+1) = 3 |
| 3 | 0 | 3 > 3? না | max(3, 3+0) = 3 |
| 4 | 4 | 4 > 3? **হ্যাঁ** | — (return False) |
index 4-এ এসে দেখা গেল 4 > furthest(3) — অর্থাৎ 4 নম্বর ঘরে পৌঁছানোই অসম্ভব, তাই সঙ্গে সঙ্গে `False`। 0 ঘরটাই দেয়াল হয়ে দাঁড়িয়েছিল।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def can_jump(nums):
"""furthest reach: শেষ ঘরে পৌঁছানো সম্ভব কিনা — এক pass greedy।"""
furthest = 0
for i, x in enumerate(nums):
if i > furthest:
return False
furthest = max(furthest, i + x)
return True
def can_jump_brute(nums):
"""সব লাফ চেষ্টা করে দেখে — ধীর কিন্তু নির্ভুল (যাচাইয়ের জন্য)।"""
n = len(nums)
def reach(i):
if i >= n - 1:
return True
for step in range(1, nums[i] + 1):
if reach(i + step):
return True
return False
return reach(0)
# --- ছোট test (সব pass করা উচিত) ---
assert can_jump([2, 3, 1, 1, 4]) is True
assert can_jump([3, 2, 1, 0, 4]) is False
assert can_jump([0]) is True
assert can_jump([0, 1]) is False
assert can_jump([2, 0, 0]) is True
assert can_jump([1, 1, 1, 1]) is True
assert can_jump([1, 0, 1, 0]) is False
# greedy আর brute force সব ছোট array-তে একমত (brute = সত্য)
import itertools
for n in range(1, 7):
for nums in itertools.product(range(0, 4), repeat=n):
assert can_jump(list(nums)) == can_jump_brute(list(nums))
print(can_jump([2, 3, 1, 1, 4])) # True
print(can_jump([3, 2, 1, 0, 4])) # False
print(can_jump([2, 0, 0])) # True
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
furthest = 0
```
শুরুতে আমরা শুধু index 0-তেই পৌঁছাতে পারি, তাই furthest = 0।
```text
for i, x in enumerate(nums):
if i > furthest:
return False
```
বাঁ থেকে ডানে প্রতিটা ঘরে যাই। যদি বর্তমান index `i` furthest-কেও ছাড়িয়ে যায়, মানে এই ঘরে পৌঁছানোই অসম্ভব — তখনই False।
```text
furthest = max(furthest, i + x)
```
এই ঘরে দাঁড়িয়ে `i + x` পর্যন্ত যাওয়া যায়; তাই furthest কে দরকার হলে বাড়িয়ে নিই। `max` মানে আগের অর্জন কখনো হারাই না।
```text
return True
```
পুরো array পার করে ফেলেছি কোথাও আটকা না পড়ে — মানে শেষ ঘর reachable।
`can_jump_brute` হলো আমাদের যাচাই-যন্ত্র — প্রতিটা সম্ভাব্য লাফ recursion-এ চেষ্টা করে। `itertools.product` দিয়ে আমরা ছোট সব array (length 1-6, value 0-3) বানিয়ে greedy আর brute-এর উত্তর মিলিয়ে দেখি — একটাও না মিললে assert চিৎকার করত।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে ছাপবে:
```text
True
False
True
সব test pass!
```
প্রথম তিন line তিনটা `print` থেকে: `[2,3,1,1,4]` → True, `[3,2,1,0,4]` → False, `[2,0,0]` → True। তার আগে সব `assert` (সরাসরি case + itertools দিয়ে শত শত random ছোট array) চুপচাপ pass করেছে, তাই শেষে `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(n)** — array-র উপর ঠিক একবার pass; প্রতিটা ঘরে constant কাজ (একটা তুলনা, একটা max)। brute force-এর exponential-এর তুলনায় আকাশ-পাতাল উন্নতি।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** — শুধু একটা `furthest` variable; কোনো বাড়তি array বা recursion stack লাগছে না।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
- **`i > furthest` চেক ভুলে যাওয়া** — এটাই early-exit; না থাকলে আটকে-পড়া ঘর ধরা পড়ে না, ভুল True আসতে পারে।
- **`>=` বনাম `>` গুলিয়ে ফেলা** — `i > furthest` সঠিক (furthest পর্যন্ত পৌঁছানো *যায়*); `i >= furthest` লিখলে valid ঘরকেও ভুলভাবে বাদ দেবে।
- **`[0]` edge case** — একটাই ঘর হলে শুরুতেই গন্তব্যে আছি, উত্তর True; অনেকে ভুলে False ভাবে।
- **শেষ index-এ লাফাতেই হবে ভাবা** — শেষ ঘরে শুধু *পৌঁছালেই* হলো, সেখান থেকে আবার লাফানোর দরকার নেই।
- **Backward দিকে ভাবা** — এই greedy বাঁ→ডান forward; উল্টোদিক থেকেও সমাধান হয় কিন্তু গুলিয়ে ফেললে logic ভাঙে।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — Jump Game II** (