105 — Gas Station¶

104-এ শিখলে "এক pass, এক সংখ্যা track" — এবার সেই একই দর্শন বৃত্তাকার রাস্তায়! Gas Station দেখতে জটিল মনে হয় (বৃত্ত, জ্বালানি, খরচ...), কিন্তু দুটো ছোট observation ধরলেই পুরো O(n²) brute force গলে এক pass-এ নেমে আসে। ধীরে পড়ো — "total ≥ 0 হলেই answer আছে" আর "reset point" — এই দুই রত্ন এখানকার আসল শিক্ষা।

Problem link ও উৎস

Original source: LeetCode — Gas Station
Platform: LeetCode — https://leetcode.com/problems/gas-station/
Topic: Greedy math tricks → reset point, prefix-sum observation
Difficulty: Medium
Pattern: reset point (tank negative হলে নতুন start)
Basic idea inherited from: 104 — Jump Game (এক pass-এ একটা সংখ্যা track)

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

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

বৃত্তাকার রাস্তায় n টা gas station সাজানো। station i-তে gas[i] পরিমাণ জ্বালানি পাবে, আর সেখান থেকে পরের station-এ যেতে cost[i] জ্বালানি খরচ হবে। তোমার গাড়ির ট্যাঙ্ক শুরুতে খালি, ধারণক্ষমতা অসীম।

তুমি কোনো এক station থেকে শুরু করে পুরো বৃত্ত ঘুরে আবার সেখানে ফিরতে চাও। প্রশ্ন: কোন station থেকে শুরু করলে এটা সম্ভব? সম্ভব হলে সেই শুরুর index, নাহলে -1।

(নিশ্চয়তা: উত্তর থাকলে সেটা একটাই — unique।)

Input ও output¶

উদাহরণ

gas              cost             ->  output  (ব্যাখ্যা)
-----------------------------------------------------------------
[1,2,3,4,5]      [3,4,5,1,2]      ->  3       (station 3 থেকে চক্কর সম্ভব)
[2,3,4]          [3,4,3]          ->  -1      (sum gain = -1 < 0, অসম্ভব)
[5]              [4]              ->  0       (একটাই station, gain +1)
[3,1,1]          [1,2,2]          ->  0       (start 0 থেকেই চলে)
[2]              [2]              ->  0       (gain 0, একটাই station — চক্করই শেষ)

মনে রাখো: sum(gas) < sum(cost) মানেই -1 (মোট জ্বালানি কম); আর answer থাকলে সেটা সবসময় unique।

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

ভাবো তুমি বৃত্তাকার একটা রাস্তায় বাইক চালিয়ে পুরো চক্কর দিতে চাও, পথে পথে পেট্রল পাম্প। কোনো পাম্প থেকে শুরু করে চলতে চলতে যদি পেট্রল ফুরিয়ে যায় (tank negative), তাহলে শুধু সেই শুরুর পাম্পই বাদ যায় না — মাঝের সব পাম্পও বাদ। কারণ মাঝের কোনো পাম্প থেকে শুরু করলে এ পর্যন্ত পথে জমানো বাড়তি পেট্রলটাই তো তুমি পেতে না, তাই আরও আগেই আটকে যেতে।

তাই বুদ্ধিমানের কাজ — যেখানে আটকালে, তার ঠিক পরের পাম্প থেকে নতুন করে চেষ্টা করা। আর মোট হিসাবে যদি পুরো রাস্তায় পাওয়া পেট্রল ≥ মোট খরচ হয়, তবে কোথাও না কোথাও থেকে শুরু করলে চক্কর সম্পূর্ণ হবেই।

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

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

সরাসরি 104 (Jump Game)-এর কাঁধে দাঁড়ানো। দুটোতেই দর্শন এক: array-র উপর এক pass, হাতে গুটিকয় সংখ্যা (এখানে total, tank, start), আর একটা চালাক observation যা সব সম্ভাবনা ঘাঁটা থেকে বাঁচায়।

104-এ track করতাম "সর্বোচ্চ কোথায় পৌঁছানো সম্ভব"; এখানে track করছি "চলন্ত ট্যাঙ্ক কখন negative হলো"। আর tank আসলে একটা prefix sum (চলন্ত যোগফল) — সেই prefix-sum-এর চিন্তা level 5 থেকেই চেনা, এখানে greedy reset-এর সাথে জুড়ে গেছে।

ভেতরের অঙ্ক¶

দুটো জিনিস। ধরো প্রতিটা station-এ লাভ-ক্ষতি gain[i] = gas[i] - cost[i]।

Total observation: পুরো বৃত্তের sum(gain) < 0 হলে কোনো start-ই কাজ করবে না (মোট জ্বালানিই খরচের চেয়ে কম); আর sum(gain) ≥ 0 হলে অন্তত একটা valid start আছেই।
Reset observation: station s থেকে শুরু করে চলতে চলতে station i-তে tank প্রথমবার negative হলে — s থেকে i পর্যন্ত মাঝের কোনো station-ই valid start নয়। তাই সোজা i + 1 থেকে নতুন করে শুরু করো।

এই দুই observation মিলিয়ে এক pass-এই উত্তর।

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

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

সরাসরি চিন্তা — প্রতিটা station কে শুরু ধরে পুরো বৃত্ত simulate করে দেখো। কোনো একটা শুরু থেকে n টা step ঘুরে আসা গেলে সেটাই উত্তর:

Python

def gas_station_brute(gas, cost):
    n = len(gas)
    for start in range(n):
        tank = 0
        ok = True
        for step in range(n):
            i = (start + step) % n
            tank += gas[i] - cost[i]
            if tank < 0:
                ok = False
                break
        if ok:
            return start
    return -1

এটা সব শুরু চেষ্টা করে দেখে, তাই সবসময় সঠিক — আমাদের যাচাইয়ের মাপকাঠি।

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

বাইরের loop n টা start, ভেতরের loop প্রতিটার জন্য n টা step — মোট O(n²)। n যদি 10⁵ হয়, তাহলে প্রায় 10¹⁰ operation — interview-তে Time Limit Exceeded।

উদাহরণ

প্রতিটা start থেকে আবার শুরু করে পুরো বৃত্ত ঘোরা মানে
একই কাজ বারবার — আগের simulate-এর তথ্য ফেলে দিচ্ছি।

brute force : O(n²)  (ধীর)
greedy      : O(n)   (এক pass — reset observation কাজ অর্ধেক করে দেয়)

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

দুই observation কাজে লাগাই। এক pass-এ total (পুরো বৃত্তের gain যোগফল) আর tank (বর্তমান চলন্ত যোগফল) রাখি; tank negative হলেই start reset করে পরের station-এ পাঠাই:

Python

def gas_station(gas, cost):
    total, tank, start = 0, 0, 0
    for i in range(len(gas)):
        gain = gas[i] - cost[i]
        total += gain
        tank += gain
        if tank < 0:
            start = i + 1     # reset: মাঝের কাউকে আর try করতে হবে না
            tank = 0
    return start if total >= 0 else -1

Greedy choice: যেখানে tank প্রথমবার negative হয়, তার ঠিক পরের station থেকে নতুন start ধরো (মাঝের সবাইকে একসাথে বাদ দাও)।

কেন কাজ করে (exchange argument, এক লাইন): ধরো optimal start কোনো station s থেকে i-এর মাঝে; কিন্তু start..i চলার সময় tank negative হয়েছে, মানে start থেকে যেকোনো মাঝের station পর্যন্ত prefix sum ≤ 0 — তাই সেই মাঝের station থেকে শুরু করলে i-তে tank আরও ছোট হতো, কখনো বড় নয়; সুতরাং মাঝের কাউকে i+1 দিয়ে বদলালে কিছু হারাই না, বরং unique optimal-টা i+1-এর পরেই থাকে।

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

দুটো এক-লাইনের "আহা!":

"চক্কর সম্ভব কিনা — পুরো বৃত্তের total gain-ই বলে দেয়; ≥ 0 হলেই answer আছে।"

"কোথাও আটকালে শুধু শুরুর station নয়, মাঝের সবাই বাদ — এক লাফে i+1-এ চলে যাও।"

এই দ্বিতীয় tweak-টাই (reset = মাঝের সবাই বাদ) O(n²)-কে O(n)-এ নামায়। প্রথমবার আটকে গিয়ে "আবার একটা একটা করে চেষ্টা করি" না ভেবে "একসাথে সব বাদ" ভাবাটাই আসল মোচড়।

ছবিতে বোঝা¶

gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2] → gain = [-2, -2, -2, 3, 3]:

উদাহরণ

station :    0    1    2    3    4
gain    :   -2   -2   -2    3    3      sum = 0  ≥ 0 → answer আছে

start=0: tank: -2 → negative! reset → start=1, tank=0
start=1: tank: -2 → negative! reset → start=2, tank=0
start=2: tank: -2 → negative! reset → start=3, tank=0
start=3: tank: 3 → 6 (ঘুরে শেষ পর্যন্ত আর negative হলো না)

total = 0 ≥ 0  ⇒  answer = start = 3  ✓

reset কীভাবে মাঝের সবাইকে একসাথে বাদ দেয়, সেই ছবি:

উদাহরণ

start=s ───X (i-তে tank negative)
   │       │
   └─ s, s+1, ..., i  সবাই বাদ  ─┘   পরের চেষ্টা: i+1 থেকে

কারণ: s থেকে i-এর মাঝের যেকোনো station থেকে শুরু করলে
      পথের জমানো বাড়তি fuel হারাতে → i-তে tank আরও কম থাকত।

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

gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2] ধীরে চালাই:

i	gain = gas[i]-cost[i]	total	tank (যোগের পর)	tank < 0?	start
0	1-3 = -2	-2	-2	হ্যাঁ → reset	1 (tank→0)
1	2-4 = -2	-4	-2	হ্যাঁ → reset	2 (tank→0)
2	3-5 = -2	-6	-2	হ্যাঁ → reset	3 (tank→0)
3	4-1 = 3	-3	3	না	3
4	5-2 = 3	0	6	না	3

loop শেষে total = 0 ≥ 0, তাই answer = start = 3। লক্ষ করো — start বারবার reset হয়ে 3-এ থিতু হলো, আর total ঠিক হিসাব রাখল উত্তর আদৌ আছে কিনা।

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

Python¶

Python

def gas_station(gas, cost):
    """reset point greedy — এক pass-এ valid start (বা -1)।"""
    total, tank, start = 0, 0, 0
    for i in range(len(gas)):
        gain = gas[i] - cost[i]
        total += gain
        tank += gain
        if tank < 0:
            start = i + 1
            tank = 0
    return start if total >= 0 else -1


def gas_station_brute(gas, cost):
    """প্রতিটা start simulate — O(n²), নির্ভুল (যাচাইয়ের জন্য)।"""
    n = len(gas)
    for start in range(n):
        tank = 0
        ok = True
        for step in range(n):
            i = (start + step) % n
            tank += gas[i] - cost[i]
            if tank < 0:
                ok = False
                break
        if ok:
            return start
    return -1


# --- ছোট test (সব pass করা উচিত) ---
assert gas_station([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]) == 3
assert gas_station([2, 3, 4], [3, 4, 3]) == -1
assert gas_station([5], [4]) == 0
assert gas_station([2], [2]) == 0
assert gas_station([3, 1, 1], [1, 2, 2]) == 0

# greedy আর brute force ছোট সব case-এ একমত (brute = সত্য)
import itertools
for n in range(1, 5):
    for gas in itertools.product(range(0, 4), repeat=n):
        for cost in itertools.product(range(0, 4), repeat=n):
            assert gas_station(list(gas), list(cost)) == gas_station_brute(list(gas), list(cost))

print(gas_station([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]))   # 3
print(gas_station([2, 3, 4], [3, 4, 3]))               # -1
print(gas_station([3, 1, 1], [1, 2, 2]))               # 0
print("সব test pass!")

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

উদাহরণ

total, tank, start = 0, 0, 0

total = পুরো বৃত্তের gain যোগফল (answer আদৌ আছে কিনা বলবে); tank = বর্তমান চলন্ত fuel; start = এখন পর্যন্ত আমাদের সেরা candidate শুরু।

উদাহরণ

gain = gas[i] - cost[i]
total += gain
tank  += gain

প্রতিটা station-এ লাভ-ক্ষতি বের করে দুই হিসাবেই যোগ করি — একটা মোট (total), একটা চলন্ত (tank)।

উদাহরণ

if tank < 0:
    start = i + 1
    tank = 0

এটাই reset-এর হৃদয়। tank negative হলে start..i সবাই বাতিল, তাই start কে i+1-এ ঠেলে দিই আর tank শূন্য করে নতুন চক্কর শুরু করি।

উদাহরণ

return start if total >= 0 else -1

total ≥ 0 হলে আমাদের শেষ candidate start-ই উত্তর (observation 1 নিশ্চয়তা দেয় এটা valid); নাহলে -1।

gas_station_brute প্রতিটা start থেকে পুরো বৃত্ত simulate করে — ধীর কিন্তু নির্ভুল। itertools.product দিয়ে ছোট সব (gas, cost) জোড়া বানিয়ে greedy আর brute মিলিয়ে দেখা হয়েছে।

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

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

উদাহরণ

3
-1
0
সব test pass!

প্রথম তিন line print থেকে: প্রথম case-এ station 3 থেকে চক্কর সম্ভব; দ্বিতীয়টায় মোট জ্বালানি কম তাই -1; তৃতীয়টায় station 0 থেকেই চলে। তার আগে সব assert (সরাসরি case + itertools দিয়ে শত শত ছোট জোড়া) চুপচাপ pass করেছে, তাই শেষে সব test pass!।

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

সময়¶

O(n) — array-র উপর ঠিক একবার pass; প্রতিটা station-এ constant কাজ। reset observation মাঝের সব station একসাথে বাদ দেয় বলে আর দ্বিতীয়বার ঘোরা লাগে না। brute force-এর O(n²) থেকে বিরাট উন্নতি।

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

O(1) — শুধু তিনটা সংখ্যা (total, tank, start); কোনো বাড়তি array নয়।

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

O(n²) brute force-এই থেমে যাওয়া — প্রতিটা start simulate করলে slow; reset observation না ধরলে এক pass-এ নামানো যায় না।
Reset-এ শুধু শুরুর station বাদ দেওয়া — tank negative হলে মাঝের সব station বাদ; start = i + 1 করতে হয়, start += 1 নয়।
total আর tank গুলিয়ে ফেলা — total শেষে answer আছে কিনা ঠিক করে; tank reset হয় বলে সে এই কাজ করতে পারে না। দুটো আলাদা রাখো।
tank reset করতে ভুলে যাওয়া — start পাল্টে tank = 0 না করলে পরের চক্করের হিসাব ভুল হবে।
Unique answer ধরে না নেওয়া — answer থাকলে একটাই; তাই প্রথম valid start-ই চূড়ান্ত, আর খুঁজতে হয় না।

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

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

LeetCode — Maximum Subarray (Kadane) (https://leetcode.com/problems/maximum-subarray/) — একই "চলন্ত যোগফল negative হলে reset" দর্শন (running sum < 0 → 0 থেকে শুরু)।
LeetCode — Jump Game (https://leetcode.com/problems/jump-game/) — এই repo-রই 104, যেখান থেকে "এক pass, এক সংখ্যা" দর্শন এসেছে।
CSES / Codeforces circular-array problem গুলো — বৃত্তাকার array-তে prefix-sum + reset-এর এই কৌশল বারবার ফেরে।

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

Reset point (prefix-sum + restart) — চলন্ত যোগফল রাখো; নির্দিষ্ট শর্তে (এখানে tank < 0) candidate reset করে পরের index-এ লাফাও, আর আলাদা একটা মোট হিসাব দিয়ে feasibility ঠিক করো। বড় শিক্ষা: "আটকে গেলে এক লাফে মাঝের সবাইকে বাদ দাও" — এই reset-ই O(n²)-কে O(n)-এ নামায়।

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

ভবিষ্যতের আমাকে এক লাইনে: "Gas Station = reset point; total gain ≥ 0 হলে answer আছে, আর tank < 0 হলেই start = i+1, tank = 0 (মাঝের সবাই বাদ)। দুই observation = এক pass O(n)।"

পরের ধাপ → 106 — Candy Distribution (এবার দুই দিকের শর্ত একসাথে সামলানো — two pass greedy)।

ফিরে দেখা: এই 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"।