104 — Jump Game¶

103-এ greedy-কে ফেল করতে দেখলে; এবার greedy যেখানে প্রমাণসহ ঠিকঠাক কাজ করে সেই স্বস্তির জায়গায় এলে। মজার ব্যাপার — এই পুরো problem-টা মাত্র একটা সংখ্যা track করেই সমাধান হয়ে যায়! সেই এক-সংখ্যার জাদুর নাম "furthest reach"। ধীরে পড়ো, এই idea-টা 105 (Gas Station)-এও সরাসরি ফিরবে।

Source¶

Original source: LeetCode — Jump Game
Platform: LeetCode — https://leetcode.com/problems/jump-game/
Topic: Greedy math tricks → furthest reachable index track করা
Difficulty: Medium
Pattern: furthest reach (এক pass-এ "সর্বোচ্চ কোথায় পৌঁছাই" track)
Basic idea inherited from: — (এই level-এর প্রথম "এক সংখ্যা track" greedy)

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-তে আটকে যাবে)।

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 না।

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।

4. Real-life analogy¶

ভাবো তুমি নদীর পাথর টপকে ওপারে যাচ্ছ। প্রতিটা পাথরে দাঁড়িয়ে তুমি দেখতে পাও সামনে সর্বোচ্চ কোন পাথর পর্যন্ত এক লাফে যাওয়া সম্ভব।

তোমার মাথায় শুধু একটা সংখ্যা রাখলেই চলে — "আমি এ পর্যন্ত যা দেখেছি, তাতে সবচেয়ে দূরের কোন পাথর পর্যন্ত পৌঁছানো সম্ভব?" কোন পাথর থেকে কোন লাফ দিলে সেখানে গেলাম — সেই ইতিহাস মনে রাখার দরকার নেই। যদি হাঁটতে হাঁটতে এমন এক পাথরে পৌঁছাও যেটা তোমার "সর্বোচ্চ পৌঁছানো সম্ভব" সীমার বাইরে, তাহলে বুঝবে — এখানে তো আসাই যেত না, ওপার অসম্ভব।

5. Visual explanation¶

nums = [2, 3, 1, 1, 4] — প্রতিটা ঘর থেকে কতদূর reach, আর furthest কীভাবে বাড়ে:

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]:

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

6. Example input and output¶

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 গুলো ধরা জরুরি।

7. Brute force thinking¶

সরাসরি চিন্তা — সব সম্ভাব্য লাফ চেষ্টা করো। কোনো ঘর থেকে 1 থেকে nums[i] পর্যন্ত প্রতিটা লাফ দিয়ে দেখো, recursion-এ এগোও; কোনো একটা path শেষ ঘরে পৌঁছালেই 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)

এটা প্রতিটা সম্ভাবনা ঘেঁটে দেখে, তাই উত্তর সবসময় সঠিক — আমরা একে greedy-র "সত্যের পরিমাপক" হিসেবে ব্যবহার করব।

8. Why brute force may be slow¶

এই recursion একই index বারবার বিভিন্ন path থেকে দেখে, তাই গাছটা exponential-ভাবে ফাঁপে। বড় array-তে (বিশেষত যেখানে সংখ্যা বড়) এটা অসহনীয় ধীর।

[2,2,2,2,...,2] টাইপ array-তে প্রতিটা ঘর থেকে 2টা শাখা —
একই ঘর বহুবার আলাদা path-এ পরিদর্শন হয়।

brute force : exponential (ধীর)
greedy      : O(n) এক pass — কারণ অপ্রয়োজনীয় তথ্য ("কোন ঘর থেকে এলাম") ফেলে দিই

9. Better thinking¶

মূল observation: "কোন ঘর থেকে লাফালাম" তথ্যটা দরকারই নেই। শুধু track করো এখন পর্যন্ত সর্বোচ্চ কোন index reachable (furthest)। বাঁ থেকে ডানে এক pass:

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)-এ নামিয়ে আনে।

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 ঘরটাই দেয়াল হয়ে দাঁড়িয়েছিল।

12. Python solution¶

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¶

furthest = 0

শুরুতে আমরা শুধু index 0-তেই পৌঁছাতে পারি, তাই furthest = 0।

for i, x in enumerate(nums):
    if i > furthest:
        return False

বাঁ থেকে ডানে প্রতিটা ঘরে যাই। যদি বর্তমান index i furthest-কেও ছাড়িয়ে যায়, মানে এই ঘরে পৌঁছানোই অসম্ভব — তখনই False।

    furthest = max(furthest, i + x)

এই ঘরে দাঁড়িয়ে i + x পর্যন্ত যাওয়া যায়; তাই furthest কে দরকার হলে বাড়িয়ে নিই। max মানে আগের অর্জন কখনো হারাই না।

return True

পুরো array পার করে ফেলেছি কোথাও আটকা না পড়ে — মানে শেষ ঘর reachable।

can_jump_brute হলো আমাদের যাচাই-যন্ত্র — প্রতিটা সম্ভাব্য লাফ recursion-এ চেষ্টা করে। itertools.product দিয়ে আমরা ছোট সব array (length 1-6, value 0-3) বানিয়ে greedy আর brute-এর উত্তর মিলিয়ে দেখি — একটাও না মিললে assert চিৎকার করত।

14. Output walkthrough¶

চালালে ছাপবে:

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

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 ভাঙে।

18. Harder problems that inherit this idea¶

LeetCode — Jump Game II (https://leetcode.com/problems/jump-game-ii/) — শুধু পৌঁছানো নয়, সর্বনিম্ন কয়টা লাফে; এখানে furthest-এর সাথে "current level boundary" যোগ হয় (BFS-সদৃশ greedy)।
LeetCode — Gas Station (https://leetcode.com/problems/gas-station/) — একই দর্শন (এক pass, এক সংখ্যা track); এটাই এই repo-র পরের problem 105।
LeetCode — Jump Game III (https://leetcode.com/problems/jump-game-iii/) — দুদিকে লাফ, তখন আর pure greedy নয়, BFS/DFS লাগে — তুলনা করার ভালো case।

19. Pattern learned¶

Furthest reach (running reachability) — array-র উপর এক pass-এ শুধু "এ পর্যন্ত সর্বোচ্চ কোথায় পৌঁছানো সম্ভব" এই একটা সংখ্যা track করা; reachable পরিসর একটানা বলেই এটা কাজ করে। বড় শিক্ষা: অপ্রয়োজনীয় তথ্য (path/ইতিহাস) ফেলে দিলেই অনেক greedy এক সংখ্যায় নেমে আসে।

20. Final summary¶

ভবিষ্যতের আমাকে এক লাইনে: "Jump Game = furthest reach; furthest = max(furthest, i + nums[i]), আর i > furthest হলেই False। 'কোন ঘর থেকে এলাম' ভুলে যাও — শুধু 'সবচেয়ে দূরে কোথায় যাওয়া যায়' রাখো।"

পরের ধাপ → 105 — Gas Station (একই এক-সংখ্যা-track দর্শন, এবার বৃত্তাকার রাস্তায় reset point)।

ফিরে দেখা: এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; কোনো problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" এমন দাবি নয় — বরং "common interview pattern" / "Google-style pattern"।