104 — Jump Game¶

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

Problem link ও উৎস

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)

প্রশ্ন ও উদাহরণ¶

সহজ করে প্রশ্ন¶

একটা 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¶

উদাহরণ

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

চেনা উদাহরণে বোঝা¶

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

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

ভিত্তির ধারণা¶

আগের কোন ধারণাটি লাগবে¶

এটা 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।

ভেতরের অঙ্ক¶

মূল idea — reachability হলো একটা একমুখী, monotone সম্পত্তি। কোন ঘর থেকে লাফালাম সেটা গুরুত্বপূর্ণ নয়; গুরুত্বপূর্ণ শুধু এখন পর্যন্ত সর্বোচ্চ কোন index পর্যন্ত পৌঁছানো সম্ভব।

এই এক সংখ্যা (furthest) ধরে রাখলেই হয়: কোনো ঘরে দাঁড়িয়ে তুমি i + nums[i] পর্যন্ত যেতে পারো, তাই furthest কে বারবার max(furthest, i + nums[i]) দিয়ে update করো। যদি কখনো এমন একটা index-এ পৌঁছাও যেটা furthest-কেও ছাড়িয়ে গেছে (i > furthest), তাহলে ওখানে আসাই অসম্ভব — answer না।

ধাপে ধাপে সমাধান¶

প্রথম সরল উপায়¶

সরাসরি চিন্তা — সব সম্ভাব্য লাফ চেষ্টা করো। কোনো ঘর থেকে 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-র "সত্যের পরিমাপক" হিসেবে ব্যবহার করব।

কোথায় বেশি কাজ হতে পারে¶

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

উদাহরণ

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

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

আরও ভালোভাবে ভাবা¶

মূল 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 ঘর হারায় না।

ভাবনার পরিবর্তন¶

এক লাইনের "আহা!":

"শেষে পৌঁছাতে পারব কিনা — এটা একটা সংখ্যাতেই ধরা: এ পর্যন্ত সবচেয়ে দূরে কোথায় পৌঁছানো সম্ভব।"

পুরো path বা "কোন ঘর থেকে কোথায় লাফালাম" — এসব অপ্রয়োজনীয় তথ্য মাথা থেকে ঝেড়ে ফেলাই tweak। অপ্রয়োজনীয় তথ্য বাদ দেওয়াই এখানে greedy-র আসল শক্তি, আর exponential brute-কে এক pass O(n)-এ নামিয়ে আনে।

ছবিতে বোঝা¶

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

ছোট input-এ ধাপে ধাপে¶

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

কোড ও ব্যাখ্যা¶

Python¶

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!")

কোডের প্রতিটি অংশ¶

উদাহরণ

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 চিৎকার করত।

Output মিলিয়ে দেখা¶

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

উদাহরণ

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

খরচ ও সাধারণ ভুল¶

সময়¶

O(n) — array-র উপর ঠিক একবার pass; প্রতিটা ঘরে constant কাজ (একটা তুলনা, একটা max)। brute force-এর exponential-এর তুলনায় আকাশ-পাতাল উন্নতি।

অতিরিক্ত জায়গা¶

O(1) — শুধু একটা furthest variable; কোনো বাড়তি array বা recursion stack লাগছে না।

যে ভুলগুলো এড়াতে হবে¶

i > furthest চেক ভুলে যাওয়া — এটাই early-exit; না থাকলে আটকে-পড়া ঘর ধরা পড়ে না, ভুল True আসতে পারে।
>= বনাম > গুলিয়ে ফেলা — i > furthest সঠিক (furthest পর্যন্ত পৌঁছানো যায়); i >= furthest লিখলে valid ঘরকেও ভুলভাবে বাদ দেবে।
[0] edge case — একটাই ঘর হলে শুরুতেই গন্তব্যে আছি, উত্তর True; অনেকে ভুলে False ভাবে।
শেষ index-এ লাফাতেই হবে ভাবা — শেষ ঘরে শুধু পৌঁছালেই হলো, সেখান থেকে আবার লাফানোর দরকার নেই।
Backward দিকে ভাবা — এই greedy বাঁ→ডান forward; উল্টোদিক থেকেও সমাধান হয় কিন্তু গুলিয়ে ফেললে logic ভাঙে।

শেখা ও পরের অনুশীলন¶

এই ধারণার পরের অনুশীলন¶

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।

কৌশলটি মনে রাখুন¶

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

নিজেকে যাচাই করুন¶

ভবিষ্যতের আমাকে এক লাইনে: "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"।