Problem link ও উৎস
- **Original source:** Grid-এ minimax shortest-path-এর classic প্রয়োগ
- **Platform:** LeetCode —
- **Topic:** graphs
- **Difficulty:** Medium
- **Pattern:** minimax Dijkstra on grid (sum নয়, path-এর সবচেয়ে বড় step minimize)
- **Basic idea inherited from:** Dijkstra (এই tracker-এর #18; দেখো [../shortest-path.md](../shortest-path.md))
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা grid দেওয়া আছে, প্রতিটা cell-এ একটা height বসানো। তুমি বাঁ-উপরের cell থেকে শুরু করে ডান-নিচের cell-এ যেতে চাও, আর প্রতি ধাপে চার দিকের (উপর/নিচ/বাঁ/ডান) যেকোনো পাশের cell-এ যেতে পারো। একটা path-এর **effort** মানে ওই path-এ পাশাপাশি দুই cell-এর height-এর পার্থক্যগুলোর মধ্যে সবচেয়ে বড়টা। তোমার কাজ এমন path বের করা যার effort সবচেয়ে ছোট, আর সেই সবচেয়ে ছোট effort-টা return করা।
```text
heights:
1 2 2
3 8 2
5 3 5
একটা path: 1 -> 2 -> 2 -> 2 -> 5 step পার্থক্য: 1,0,0,3 -> effort 3
ভালো path: 1 -> 3 -> 5 -> 3 -> 5 step পার্থক্য: 2,2,2,2 -> effort 2 <- উত্তর
```
### Input ও output {#8-example-input-and-output}
```text
Input : heights = [[1,2,2],[3,8,2],[5,3,5]]
Output: 2
Input : heights = [[1,2,3],[3,8,4],[5,3,5]]
Output: 1
Edge case (একটাই cell, কোনো move নেই): heights = [[1]] -> 0
Edge case (এক সারি): heights = [[1,10,6,7,9,10,4,9]] -> 9
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তুমি গাড়ি নিয়ে পাহাড়ি রাস্তায় যাচ্ছ, আর তোমার গাড়ির একটা দুর্বলতা আছে — খুব খাড়া চড়াই/উতরাই হলে engine গরম হয়ে যায়। তুমি চাও এমন রাস্তা যেখানে সবচেয়ে খাড়া অংশটা যতটা সম্ভব কম খাড়া। মোট কত উঠলে-নামলে সেটা তোমার মাথাব্যথা না; তোমার একমাত্র চিন্তা — পুরো যাত্রায় সবচেয়ে বাজে ধাক্কাটা কত। সেটাই minimax: সবচেয়ে বড় step-টা minimize করা।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা সরাসরি **Dijkstra**-র উপর দাঁড়িয়ে (#18, Network Delay Time)। Dijkstra-তে তুমি সবসময় "এখন পর্যন্ত জানা সবচেয়ে সস্তা" frontier node আগে expand করো, আর সেই cost final হয়ে যায়। এখানেও ঠিক সেটাই, শুধু "cost" মানে edge-গুলোর যোগফল নয় — "এ পর্যন্ত path-এর সবচেয়ে বড় single step"। [../shortest-path.md](../shortest-path.md)-এর "queue → deque → heap" progression-এর শেষ ধাপ, একটা ছোট মোচড় সহ।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: path-এর cost কীভাবে মাপছি, সেটাই বদলে গেছে। সাধারণ Dijkstra-তে একটা edge যোগ করলে cost হয় `old_cost + w` — যোগফল। এখানে একটা edge যোগ করলে নতুন cost হয় `max(old_cost, step)` — অর্থাৎ এ পর্যন্ত যা ছিল আর এই নতুন step, দুটোর মধ্যে বড়টা। মূল invariant টিকে থাকে কারণ `max` কখনো কমে না: path বাড়ালে cost হয় একই থাকে নয় বাড়ে, কখনো কমে না। এই "extension কখনো সস্তা করে না" শর্তটাই Dijkstra-র safety proof-এর প্রাণ ([../shortest-path.md](../shortest-path.md)), তাই greedy choice এখানেও বৈধ।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **min-heap** (Python-এ `heapq`)। সাথে grid-এর adjacency implicit — চার দিকের neighbor নিয়ম দিয়েই বের হয়, আলাদা list বানাতে হয় না। আর প্রতিটা cell-এ "এ পর্যন্ত জানা সবচেয়ে ছোট effort" রাখার জন্য একটা 2D `effort` table।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Min-heap fit করে কারণ প্রতিটা step-এ আমাদের দরকার "সব জানা frontier-এর মধ্যে সবচেয়ে ছোট effort-ওয়ালা cell"। Heap সেই minimum O(log n)-এ দেয়, যেটা plain queue পারে না (queue insertion-order দেয়, cost-order না)। যেহেতু weight-এর জায়গায় `max`-based cost কখনো negative দিকে যায় না, Dijkstra-র greedy frontier ঠিক কাজ করে — তাই heap-ই সঠিক tool, Bellman-Ford-এর ধীর pass লাগে না।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: সব possible path explore করো (DFS/backtracking দিয়ে), প্রতিটা path-এর max step হিসাব করো, সবগুলোর মধ্যে সবচেয়ে ছোটটা রাখো।
```text
1) (0,0) থেকে DFS শুরু করো, এ পর্যন্ত path-এর max step বহন করো
2) destination-এ পৌঁছালে সেই max step-টা candidate answer-এ রাখো
3) সব path শেষ হলে সবচেয়ে ছোট candidate-টাই উত্তর
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
Grid-এ path-এর সংখ্যা exponential — প্রতিটা cell থেকে কয়েক দিকে যাওয়া যায়, তাই সব path গুনলে সময় বিস্ফোরিত হয়ে যায় (এমনকি cycle এড়াতে visited সামলালেও বহু path থাকে)। একই cell বহুবার বহু path-এর অংশ হিসেবে আবার আবার visit হয়, যেখানে আসলে দরকার শুধু "এই cell-এ পৌঁছানোর সবচেয়ে ভালো (ছোট) effort"। সেই পুনরাবৃত্তিই Dijkstra বন্ধ করে।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: এটা shortest-path problem-ই — শুধু path-এর "দৈর্ঘ্য"-এর সংজ্ঞা বদলেছে। যোগফলের বদলে এখন cost = path বরাবর সবচেয়ে বড় step। আর যেহেতু একটা step যোগ করলে এই max কখনো কমে না, Dijkstra-র greedy frontier (সবচেয়ে সস্তা আগে, একবার final হলে আর বদলায় না) এখানেও নিরাপদ।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
Dijkstra চালাও, কিন্তু relax-এর সূত্র বদলে দাও। সাধারণ Dijkstra: `new = cost + w`। এখানে: `new = max(cost, step)`। Heap থেকে সবচেয়ে ছোট effort-ওয়ালা cell pop করো; destination প্রথমবার pop হলেই সেটাই উত্তর, কারণ ওই মুহূর্তে তার effort প্রমাণিতভাবে final (frontier-এর বাকি সবার effort ≥ এটা, আর extension শুধু সমান বা বড় করে)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "মোট কত উঠতে-নামতে হবে" ভাবা বন্ধ করো; ভাবো "পুরো path-এ সবচেয়ে বড় ধাক্কাটা কত, আর সেটাকে ছোট করব।" এই এক শব্দ বদল — `sum` থেকে `max` — সাধারণ Dijkstra-কে minimax Dijkstra বানিয়ে দেয়, বাকি সব কাঠামো একই থাকে।
### ছবিতে বোঝা {#7-visual-explanation}
`heights = [[1,2,2],[3,8,2],[5,3,5]]`, heap-এ `(এ পর্যন্ত max step, r, c)`:
```text
start (0,0) height 1, effort=0
pop (0, 0,0): neighbors
(0,1) step|2-1|=1 -> push (1, 0,1)
(1,0) step|3-1|=2 -> push (2, 1,0)
heap: (1,0,1) (2,1,0)
pop (1, 0,1) height 2:
(0,2) step 0 -> max(1,0)=1 push (1,0,2)
(1,1) step 6 -> max(1,6)=6 push (6,1,1)
heap: (1,0,2) (2,1,0) (6,1,1)
pop (1, 0,2) height 2:
(1,2) step 0 -> max(1,0)=1 push (1,1,2)
heap: (1,1,2) (2,1,0) (6,1,1)
pop (1,1,2): (2,2)-এর candidate=max(1,3)=3 -> push (3,2,2)
pop (2,1,0): (2,0)-এর effort=2; (1,1)-এর effort 6 থেকে 5
heap: (2,2,0) (3,2,2) (5,1,1) (6,1,1)
pop (2,2,0): (2,1)-এর candidate=max(2,2)=2 -> push (2,2,1)
pop (2,2,1): (2,2)-এর effort 3 থেকে 2; (1,1)-এর candidate 5, উন্নতি নেই
heap: (2,2,2) (3,2,2) (5,1,1) (6,1,1)
pop (2,2,2): destination, উত্তর 2; এখন থামা নিরাপদ।
পুরোনো (3,2,2) ও (6,1,1) entries আর process করতে হবে না।
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
ছোট input `heights = [[1,2],[1,3]]` (উত্তর হওয়া উচিত 1):
1. শুরু: `effort` সব `inf`, `effort[0][0]=0`, heap `[(0,0,0)]`।
2. pop `(0,0,0)` height 1। neighbor `(0,1)` step `|2-1|=1` → push `(1,0,1)`; neighbor `(1,0)` step `|1-1|=0` → push `(0,1,0)`। heap: `(0,1,0) (1,0,1)`।
3. pop `(0,1,0)` height 1। neighbor `(1,1)` step `|3-1|=2` → `max(0,2)=2` push `(2,1,1)`; `(0,0)` already ভালো। heap: `(1,0,1) (2,1,1)`।
4. pop `(1,0,1)` height 2। neighbor `(1,1)` step `|3-2|=1` → `max(1,1)=1` push `(1,1,1)`। heap: `(1,1,1) (2,1,1)`।
5. pop `(1,1,1)` — এটাই destination `(1,1)`, effort `1` → return `1`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
import heapq
def minimum_effort_path(heights):
# minimax Dijkstra: path-এর সবচেয়ে বড় step-difference minimize করো
rows, cols = len(heights), len(heights[0])
# effort[r][c] = এই cell-এ পৌঁছাতে এখন পর্যন্ত জানা সবচেয়ে ছোট "max step"
effort = [[float("inf")] * cols for _ in range(rows)]
effort[0][0] = 0
heap = [(0, 0, 0)] # (path-এর max step, row, col)
while heap:
e, r, c = heapq.heappop(heap)
if (r, c) == (rows - 1, cols - 1): # destination first pop = answer
return e
if e > effort[r][c]:
continue # stale entry, lazy skip
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols:
step = abs(heights[nr][nc] - heights[r][c])
new_e = max(e, step) # path cost = সবচেয়ে বড় single step
if new_e < effort[nr][nc]:
effort[nr][nc] = new_e
heapq.heappush(heap, (new_e, nr, nc))
return 0
# ---- tests ----
assert minimum_effort_path([[1, 2, 2], [3, 8, 2], [5, 3, 5]]) == 2
assert minimum_effort_path([[1, 2, 3], [3, 8, 4], [5, 3, 5]]) == 1
assert minimum_effort_path([[1, 2, 1, 1, 1], [1, 2, 1, 2, 1], [1, 2, 1, 2, 1], [1, 2, 1, 2, 1], [1, 1, 1, 2, 1]]) == 0
assert minimum_effort_path([[1]]) == 0
assert minimum_effort_path([[1, 10, 6, 7, 9, 10, 4, 9]]) == 9
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `effort = [[inf]...]` — প্রতিটা cell-এ এখন পর্যন্ত জানা সবচেয়ে ছোট "max step"; শুরুতে অজানা মানে infinity।
- `effort[0][0] = 0` — শুরুর cell-এ কোনো step নেওয়া হয়নি, তাই effort 0।
- `heap = [(0, 0, 0)]` — `(cost, row, col)`; cost আগে রাখা জরুরি, নাহলে heap row দিয়ে sort করবে।
- `if (r, c) == (rows-1, cols-1): return e` — destination প্রথমবার pop হলেই effort final, সঙ্গে সঙ্গে return।
- `if e > effort[r][c]: continue` — lazy deletion: পুরোনো (stale) heap entry বাদ দাও ([../shortest-path.md](../shortest-path.md)-এর trick)।
- `step = abs(...)` — পাশের cell-এ যেতে height-এর পার্থক্য, অর্থাৎ এই edge-এর "ওজন"।
- `new_e = max(e, step)` — মূল মোচড়: path cost যোগফল নয়, এ পর্যন্ত max আর এই step-এর মধ্যে বড়টা।
- `if new_e < effort[nr][nc]` — আরও ভালো (ছোট) effort পেলেই relax করে নতুন entry push।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`minimum_effort_path([[1,2,2],[3,8,2],[5,3,5]])`: heap সবসময় সবচেয়ে ছোট effort-ওয়ালা cell আগে ছাড়ে। 8-ওয়ালা cell (1,1)-এ ঢুকতে গেলে step অন্তত 5/6 লাগে, তাই algorithm সেটা এড়িয়ে বাঁ আর নিচের প্রান্ত ধরে যায়, যেখানে সবচেয়ে বড় step মাত্র 2। destination `(2,2)` effort 2 নিয়ে pop হয় → return 2। বাকি সব assert pass, শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(R·C·log(R·C))** — grid-এ `R·C` টা cell, প্রতিটা cell heap-এ কয়েকবার push হতে পারে, প্রতিটা heap operation `log(R·C)`। এটা edge সংখ্যা `O(R·C)` (প্রতি cell-এ 4 neighbor) ধরে standard Dijkstra খরচ।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(R·C)** — `effort` table-এ প্রতিটা cell-এর জন্য একটা entry, আর heap-এও সবচেয়ে বেশি `O(R·C)` entry জমতে পারে।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- Relax-এ ভুল করে `e + step` লেখা (যোগফল), অথচ এই problem-এ `max(e, step)` চাই — তাহলে উত্তর সম্পূর্ণ ভুল।
- `(cost, r, c)`-এর বদলে `(r, c, cost)` push করা — heap তখন row দিয়ে sort করে, Dijkstra ভেঙে পড়ে।
- destination pop-এ return না করে পুরো heap শেষ করা — সঠিক হলেও অপ্রয়োজনীয় কাজ; first pop-ই final।
- `if e > effort[r][c]: continue` বাদ দেওয়া — correctness টিকে যায় কিন্তু stale entry গুলো re-expand হয়ে ধীর হয়।
- grid boundary check (`0 <= nr < rows`) ভুলে index out of range।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: **Dijkstra** (#18, Network Delay Time; [../shortest-path.md](../shortest-path.md))। ওখানে cost ছিল edge-weight-এর যোগফল; এখানে cost হলো path বরাবর সবচেয়ে বড় step। আটকে গেলে আগে plain Dijkstra-র heap + lazy-skip কাঠামোটা মনে করো, তারপর শুধু relax-এর সূত্রটা `sum` থেকে `max`-এ বদলাও — অর্ধেক উত্তর সেখানেই।
### পরের অনুশীলন {#22-similar-harder-problems}
- Swim in Rising Water (একই minimax Dijkstra, একটু ভিন্ন cost) —