020 — Path With Minimum Effort

Source

• Original source: Grid-এ minimax shortest-path-এর classic প্রয়োগ
• Platform: LeetCode — https://leetcode.com/problems/path-with-minimum-effort/
• Topic: graphs
• Difficulty: Medium
• Pattern: minimax Dijkstra on grid (sum নয়, path-এর সবচেয়ে বড় step minimize)
• Basic idea inherited from: Dijkstra (এই tracker-এর #18; দেখো ../shortest-path.md)

1. Problem in simple words

তোমাকে একটা grid দেওয়া আছে, প্রতিটা cell-এ একটা height বসানো। তুমি বাঁ-উপরের cell থেকে শুরু করে ডান-নিচের cell-এ যেতে চাও, আর প্রতি ধাপে চার দিকের (উপর/নিচ/বাঁ/ডান) যেকোনো পাশের cell-এ যেতে পারো। একটা path-এর effort মানে ওই path-এ পাশাপাশি দুই cell-এর height-এর পার্থক্যগুলোর মধ্যে সবচেয়ে বড়টা। তোমার কাজ এমন path বের করা যার effort সবচেয়ে ছোট, আর সেই সবচেয়ে ছোট effort-টা return করা।

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  <- উত্তর

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-এর "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), তাই 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 লাগে না।

6. Real-life analogy

ভাবো তুমি গাড়ি নিয়ে পাহাড়ি রাস্তায় যাচ্ছ, আর তোমার গাড়ির একটা দুর্বলতা আছে — খুব খাড়া চড়াই/উতরাই হলে engine গরম হয়ে যায়। তুমি চাও এমন রাস্তা যেখানে সবচেয়ে খাড়া অংশটা যতটা সম্ভব কম খাড়া। মোট কত উঠলে-নামলে সেটা তোমার মাথাব্যথা না; তোমার একমাত্র চিন্তা — পুরো যাত্রায় সবচেয়ে বাজে ধাক্কাটা কত। সেটাই minimax: সবচেয়ে বড় step-টা minimize করা।

7. Visual explanation

heights = [[1,2,2],[3,8,2],[5,3,5]], heap-এ (এ পর্যন্ত max step, r, c):

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)
... শেষমেশ (2,2) destination pop হয় effort 2 নিয়ে -> answer 2

8. Example input and output

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

9. Brute force thinking

প্রথম সরল চিন্তা: সব possible path explore করো (DFS/backtracking দিয়ে), প্রতিটা path-এর max step হিসাব করো, সবগুলোর মধ্যে সবচেয়ে ছোটটা রাখো।

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 বানিয়ে দেয়, বাকি সব কাঠামো একই থাকে।

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।

15. Python solution

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-এর 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।

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

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।

21. Which basic problem this inherits from

ভিত্তি: Dijkstra (#18, Network Delay Time; ../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) — https://leetcode.com/problems/swim-in-rising-water/ (এই tracker-এর #25)
• Network Delay Time (সাধারণ sum Dijkstra) — https://leetcode.com/problems/network-delay-time/ (#18)
• Path With Maximum Minimum Value (max-min variant, একই idea উল্টো দিকে) — https://leetcode.com/problems/path-with-maximum-minimum-value/

23. Pattern learned

Minimax Dijkstra: যখন path-এর "খরচ" মানে যোগফল নয় বরং "সবচেয়ে বড় (বা সবচেয়ে ছোট) single step", তখন Dijkstra-র relax-এ + বদলে max (বা min) বসাও — বাকি সব কাঠামো অপরিবর্তিত।

24. Final summary

ভবিষ্যতের আমাকে: "'path-এর সবচেয়ে বড় ধাক্কা minimize করো' = minimax Dijkstra; heap-এ (max_step, r, c), relax-এ max(cost, step), destination first pop = answer।" 'minimum possible maximum along a path' এই ধরনের শব্দ দেখলেই Dijkstra-র max-variant মনে পড়বে।

---

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