Problem link ও উৎস
- **Original source:** LeetCode — Gas Station
- **Platform:** LeetCode —
- **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)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
বৃত্তাকার রাস্তায় `n` টা gas station সাজানো। station `i`-তে `gas[i]` পরিমাণ জ্বালানি পাবে, আর সেখান থেকে পরের station-এ যেতে `cost[i]` জ্বালানি খরচ হবে। তোমার গাড়ির ট্যাঙ্ক শুরুতে খালি, ধারণক্ষমতা অসীম।
তুমি কোনো এক station থেকে শুরু করে **পুরো বৃত্ত ঘুরে আবার সেখানে ফিরতে** চাও। প্রশ্ন: **কোন station থেকে শুরু করলে** এটা সম্ভব? সম্ভব হলে সেই শুরুর index, নাহলে -1।
(নিশ্চয়তা: উত্তর থাকলে সেটা একটাই — unique।)
### Input ও output {#6-example-input-and-output}
```text
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।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো তুমি বৃত্তাকার একটা রাস্তায় বাইক চালিয়ে পুরো চক্কর দিতে চাও, পথে পথে পেট্রল পাম্প। কোনো পাম্প থেকে শুরু করে চলতে চলতে যদি **পেট্রল ফুরিয়ে যায়** (tank negative), তাহলে শুধু সেই শুরুর পাম্পই বাদ যায় না — **মাঝের সব পাম্পও** বাদ। কারণ মাঝের কোনো পাম্প থেকে শুরু করলে এ পর্যন্ত পথে জমানো বাড়তি পেট্রলটাই তো তুমি পেতে না, তাই আরও আগেই আটকে যেতে।
তাই বুদ্ধিমানের কাজ — যেখানে আটকালে, তার ঠিক **পরের** পাম্প থেকে নতুন করে চেষ্টা করা। আর মোট হিসাবে যদি পুরো রাস্তায় পাওয়া পেট্রল ≥ মোট খরচ হয়, তবে কোথাও না কোথাও থেকে শুরু করলে চক্কর সম্পূর্ণ হবেই।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
সরাসরি 104 (Jump Game)-এর কাঁধে দাঁড়ানো। দুটোতেই দর্শন এক: **array-র উপর এক pass, হাতে গুটিকয় সংখ্যা (এখানে `total`, `tank`, `start`), আর একটা চালাক observation যা সব সম্ভাবনা ঘাঁটা থেকে বাঁচায়।**
104-এ track করতাম "সর্বোচ্চ কোথায় পৌঁছানো সম্ভব"; এখানে track করছি "চলন্ত ট্যাঙ্ক কখন negative হলো"। আর `tank` আসলে একটা prefix sum (চলন্ত যোগফল) — সেই prefix-sum-এর চিন্তা level 5 থেকেই চেনা, এখানে greedy reset-এর সাথে জুড়ে গেছে।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
দুটো জিনিস। ধরো প্রতিটা 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-এই উত্তর।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সরাসরি চিন্তা — **প্রতিটা 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
```
এটা সব শুরু চেষ্টা করে দেখে, তাই সবসময় সঠিক — আমাদের যাচাইয়ের মাপকাঠি।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
বাইরের loop n টা start, ভেতরের loop প্রতিটার জন্য n টা step — মোট **O(n²)**। n যদি 10⁵ হয়, তাহলে প্রায় 10¹⁰ operation — interview-তে Time Limit Exceeded।
```text
প্রতিটা start থেকে আবার শুরু করে পুরো বৃত্ত ঘোরা মানে
একই কাজ বারবার — আগের simulate-এর তথ্য ফেলে দিচ্ছি।
brute force : O(n²) (ধীর)
greedy : O(n) (এক pass — reset observation কাজ অর্ধেক করে দেয়)
```
### আরও ভালোভাবে ভাবা {#9-better-thinking}
দুই 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`-এর পরেই থাকে।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
দুটো এক-লাইনের "আহা!":
> ১. "চক্কর সম্ভব কিনা — পুরো বৃত্তের total gain-ই বলে দেয়; ≥ 0 হলেই answer আছে।"
>
> ২. "কোথাও আটকালে শুধু শুরুর station নয়, মাঝের সবাই বাদ — এক লাফে i+1-এ চলে যাও।"
এই দ্বিতীয় tweak-টাই (reset = মাঝের সবাই বাদ) O(n²)-কে O(n)-এ নামায়। প্রথমবার আটকে গিয়ে "আবার একটা একটা করে চেষ্টা করি" না ভেবে "একসাথে সব বাদ" ভাবাটাই আসল মোচড়।
### ছবিতে বোঝা {#5-visual-explanation}
`gas = [1, 2, 3, 4, 5]`, `cost = [3, 4, 5, 1, 2]` → `gain = [-2, -2, -2, 3, 3]`:
```text
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 কীভাবে মাঝের সবাইকে একসাথে বাদ দেয়, সেই ছবি:
```text
start=s ───X (i-তে tank negative)
│ │
└─ s, s+1, ..., i সবাই বাদ ─┘ পরের চেষ্টা: i+1 থেকে
কারণ: s থেকে i-এর মাঝের যেকোনো station থেকে শুরু করলে
পথের জমানো বাড়তি fuel হারাতে → i-তে tank আরও কম থাকত।
```
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`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 ঠিক হিসাব রাখল উত্তর আদৌ আছে কিনা।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```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!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
total, tank, start = 0, 0, 0
```
`total` = পুরো বৃত্তের gain যোগফল (answer আদৌ আছে কিনা বলবে); `tank` = বর্তমান চলন্ত fuel; `start` = এখন পর্যন্ত আমাদের সেরা candidate শুরু।
```text
gain = gas[i] - cost[i]
total += gain
tank += gain
```
প্রতিটা station-এ লাভ-ক্ষতি বের করে দুই হিসাবেই যোগ করি — একটা মোট (total), একটা চলন্ত (tank)।
```text
if tank < 0:
start = i + 1
tank = 0
```
এটাই reset-এর হৃদয়। tank negative হলে `start..i` সবাই বাতিল, তাই `start` কে `i+1`-এ ঠেলে দিই আর tank শূন্য করে নতুন চক্কর শুরু করি।
```text
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 মিলিয়ে দেখা {#14-output-walkthrough}
চালালে ছাপবে:
```text
3
-1
0
সব test pass!
```
প্রথম তিন line `print` থেকে: প্রথম case-এ station 3 থেকে চক্কর সম্ভব; দ্বিতীয়টায় মোট জ্বালানি কম তাই -1; তৃতীয়টায় station 0 থেকেই চলে। তার আগে সব `assert` (সরাসরি case + itertools দিয়ে শত শত ছোট জোড়া) চুপচাপ pass করেছে, তাই শেষে `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(n)** — array-র উপর ঠিক একবার pass; প্রতিটা station-এ constant কাজ। reset observation মাঝের সব station একসাথে বাদ দেয় বলে আর দ্বিতীয়বার ঘোরা লাগে না। brute force-এর O(n²) থেকে বিরাট উন্নতি।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** — শুধু তিনটা সংখ্যা (`total`, `tank`, `start`); কোনো বাড়তি array নয়।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
- **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-ই চূড়ান্ত, আর খুঁজতে হয় না।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — Maximum Subarray (Kadane)** (