Skip to content

025 — Swim in Rising Water

Source

  • Original source: Grid-এ minimax shortest-path-এর classic প্রয়োগ
  • Platform: LeetCode — https://leetcode.com/problems/swim-in-rising-water/
  • Topic: graphs
  • Difficulty: Hard
  • Pattern: minimax Dijkstra (path বরাবর সর্বোচ্চ elevation minimize)
  • Basic idea inherited from: minimax Dijkstra (এই tracker-এর #20); পরে আবার করো ../../10-disjoint-set-union/ দিয়ে

1. Problem in simple words

তোমাকে n × n একটা grid দেওয়া আছে; প্রতিটা cell-এ একটা সংখ্যা — সেই জায়গার উচ্চতা (elevation)। সময় t-তে জলের স্তর t। তুমি কোনো cell-এ থাকতে বা সেখানে সাঁতরে যেতে পারো শুধু তখনই, যখন জলের স্তর সেই cell-এর elevation-এর সমান বা বেশি — অর্থাৎ সেই cell ডুবে গেছে। তুমি বাঁ-উপরের cell (0,0) থেকে শুরু করে ডান-নিচের cell (n-1,n-1)-এ পৌঁছাতে চাও (চার পাশে চলা যায়)। সবচেয়ে কম কোন সময়ে পৌঁছানো সম্ভব, সেটা বের করো।

grid:
  0  2
  1  3

t=3-এ পথ 0 -> 1 -> 3  (অথবা 0 -> 2 -> 3): এই path-এ সর্বোচ্চ elevation 3
আগে (t<3) destination 3 ডোবেই না।
উত্তর: 3

2. Which basic idea does this inherit from?

এটা সরাসরি minimax Dijkstra-র উপর দাঁড়িয়ে (#20, Path With Minimum Effort)। #20-এ path-এর cost ছিল পাশাপাশি cell-এর height-পার্থক্যের সর্বোচ্চ; এখানে cost হলো path বরাবর cell-গুলোর elevation-এর সর্বোচ্চ। কারণ কোনো path ধরে যেতে গেলে অপেক্ষা করতে হবে যতক্ষণ না সেই path-এর সবচেয়ে উঁচু cell-টাও ডোবে — তাই সময় = path-এর max elevation, আর আমরা সেই max-কে minimize করতে চাই। ../shortest-path.md-এর শেষ trigger: "minimum possible maximum along a path (minimax)।"

3. What is the hidden math or logic?

লুকানো logic: "সময়" আর "path-এর max elevation" আসলে এক জিনিস। সময় t-তে কেবল সেইসব cell ব্যবহারযোগ্য যাদের elevation ≤ t। তাই (0,0) থেকে (n-1,n-1)-এ যাওয়ার ন্যূনতম সময় = সেই path-এর max elevation যেটার max-elevation সবচেয়ে ছোট। এটাই minimax shortest path। আর invariant যেটা Dijkstra-কে বৈধ রাখে: path বাড়ালে তার max elevation কখনো কমে না (max একমুখী) — তাই "cheapest known first, একবার final হলে আর বদলায় না" greedy নিরাপদ (../shortest-path.md-এর safety proof)।

4. Which data structure is needed?

একটা min-heap (heapq), grid-এর implicit adjacency (চার দিকের neighbor), আর একটা 2D visited array — কোনো cell-এর final (সবচেয়ে ছোট max-elevation) একবার বের হয়ে গেলে আবার process না করতে।

5. Why this data structure fits

Min-heap fit করে কারণ প্রতি ধাপে দরকার "সব frontier cell-এর মধ্যে সবচেয়ে ছোট path-max-elevation-ওয়ালা cell"; heap সেটা O(log n)-এ দেয়। যেহেতু max-based cost কখনো কমে না, Dijkstra-র greedy frontier সঠিক — তাই Bellman-Ford-এর ধীর pass লাগে না, heap-ই যথেষ্ট। visited array fit করে কারণ একবার কোনো cell সবচেয়ে কম সময়ে পৌঁছানো প্রমাণ হলে তাকে আবার expand করা শুধু অপচয়।

6. Real-life analogy

ভাবো একটা নিচু জমিতে বৃষ্টিতে আস্তে আস্তে জল জমছে। তুমি এক কোণ থেকে আরেক কোণে সাঁতরে যেতে চাও, কিন্তু কোনো জায়গা পার হতে পারবে কেবল যখন সেটা জলে ডুবেছে। উঁচু ঢিবিগুলো সবচেয়ে দেরিতে ডোবে। তোমার যাত্রার সবচেয়ে উঁচু ঢিবিটাই ঠিক করে দেয় কখন তুমি পুরো পথ পেরোতে পারবে। তাই তুমি এমন পথ খোঁজো যার সবচেয়ে উঁচু ঢিবিটা যতটা সম্ভব নিচু — সেটাই সবচেয়ে কম অপেক্ষা।

7. Visual explanation

grid = [[0,2],[1,3]], heap-এ (এ পর্যন্ত path-এর max elevation, r, c):

start (0,0) elevation 0
pop (0, 0,0): neighbors
   (0,1) elev 2 -> push (max(0,2)=2, 0,1)
   (1,0) elev 1 -> push (max(0,1)=1, 1,0)
heap: (1,1,0) (2,0,1)

pop (1, 1,0) elevation 1:
   (1,1) elev 3 -> push (max(1,3)=3, 1,1)
heap: (2,0,1) (3,1,1)

pop (2, 0,1) elevation 2:
   (1,1) elev 3 -> push (max(2,3)=3, 1,1)
heap: (3,1,1) (3,1,1)

pop (3, 1,1): destination! return 3

8. Example input and output

Input : grid = [[0,2],[1,3]]
Output: 3

Input : grid = [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
Output: 16

Edge case (একটাই cell): grid = [[0]] -> 0
Edge case (start-ই উঁচু): grid = [[3,2],[0,1]] -> 3   (start 3, পুরো path-এর max অন্তত 3)

9. Brute force thinking

প্রথম সরল চিন্তা: উত্তরের উপর binary search। একটা সময় t ধরো; শুধু elevation ≤ t cell ব্যবহার করে (0,0) থেকে (n-1,n-1)-এ DFS/BFS-এ পৌঁছানো যায় কিনা দেখো। যায় হলে t ছোট করার চেষ্টা করো, না গেলে বড় করো — সবচেয়ে ছোট সম্ভব t-ই উত্তর।

1) lo=grid[0][0], hi=max elevation
2) mid = (lo+hi)//2; elevation<=mid cell দিয়ে reachable?
3) reachable -> hi=mid ; নাহলে lo=mid+1
4) lo == উত্তর

10. Why brute force is slow

binary-search-plus-flood approach ভুল নয় (O(n^2 log(maxElev))) — কিন্তু প্রতিটা candidate t-এর জন্য পুরো grid নতুন করে flood করতে হয়, একই কাজ বারবার। Dijkstra সেটা এক পাসেই করে: প্রতিটা cell-এর "সবচেয়ে ছোট path-max" সরাসরি বের করে, বারবার reachability পরীক্ষা ছাড়াই। মূল অপচয়: একই grid-কে বহু t-এর জন্য আবার আবার explore করা, যেখানে minimax Dijkstra তথ্যটা একবারেই জমিয়ে ফেলে।

11. Key observation

মূল observation: সময় t-তে পৌঁছানোর শর্ত = এমন path থাকা যার সব cell-এর elevation ≤ t, অর্থাৎ যার max elevation ≤ t। তাই ন্যূনতম সময় = সব path-এর মধ্যে সবচেয়ে ছোট "max elevation"। এটা ঠিক minimax shortest path — Dijkstra দিয়ে relax-এ max বসিয়ে সরাসরি বের হয়।

12. Optimized intuition

Dijkstra চালাও, কিন্তু path-cost = path বরাবর সর্বোচ্চ elevation। heap-এ (এ পর্যন্ত max elevation, r, c) রাখো, শুরুতে (grid[0][0], 0, 0)। সবচেয়ে ছোট max-elevation-ওয়ালা cell pop করো; neighbor-এ গেলে নতুন cost = max(এ পর্যন্ত, neighbor-এর elevation)। destination প্রথমবার pop হলেই সেটাই উত্তর — কারণ ওই মুহূর্তে তার path-max প্রমাণিতভাবে সবচেয়ে ছোট (frontier-এর বাকিরা ≥, আর extension শুধু সমান/বড় করে)।

13. Thinking tweak

মোচড়: "সময়" শব্দটা যেন বিভ্রান্ত না করে — সময় t-তে যাওয়া যায় মানে path-এর সব cell ≤ t, মানে path-এর max ≤ t। তাই "ন্যূনতম সময়" = "সবচেয়ে ছোট path-max-elevation" = minimax Dijkstra। #20-এর সাথে একমাত্র পার্থক্য: cost-এ step-পার্থক্যের বদলে cell-এর নিজের elevation।

14. Step-by-step dry run

grid = [[0,2],[1,3]] (উত্তর 3):

  1. visited সব False। heap [(0, 0, 0)] (start elevation 0)।
  2. pop (0, 0,0)। destination নয়, mark visited। neighbor (0,1) elev 2 → push (2,0,1); (1,0) elev 1 → push (1,1,0)। heap [(1,1,0),(2,0,1)]।
  3. pop (1, 1,0)। mark visited। neighbor (1,1) elev 3 → push (max(1,3)=3, 1,1)। heap [(2,0,1),(3,1,1)]।
  4. pop (2, 0,1)। mark visited। neighbor (1,1) elev 3 → push (3,1,1)। heap [(3,1,1),(3,1,1)]।
  5. pop (3, 1,1) — এটাই destination (1,1) → return 3।

15. Python solution

import heapq

def swim_in_water(grid):
    # minimax Dijkstra: time = path বরাবর cell-গুলোর সর্বোচ্চ elevation
    n = len(grid)
    visited = [[False] * n for _ in range(n)]
    heap = [(grid[0][0], 0, 0)]                # (এ পর্যন্ত path-এর max elevation, r, c)
    while heap:
        t, r, c = heapq.heappop(heap)
        if (r, c) == (n - 1, n - 1):
            return t                            # destination first pop = answer
        if visited[r][c]:
            continue
        visited[r][c] = True
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and not visited[nr][nc]:
                # নতুন path-cost = পুরোনো max আর নতুন cell-এর max
                heapq.heappush(heap, (max(t, grid[nr][nc]), nr, nc))
    return -1

# ---- tests ----
assert swim_in_water([[0, 2], [1, 3]]) == 3
assert swim_in_water([[0, 1, 2, 3, 4], [24, 23, 22, 21, 5], [12, 13, 14, 15, 16], [11, 17, 18, 19, 20], [10, 9, 8, 7, 6]]) == 16
assert swim_in_water([[0]]) == 0
assert swim_in_water([[3, 2], [0, 1]]) == 3
print("সব test pass!")

16. Line-by-line code explanation

  • visited = [[False]*n ...] — প্রতিটা cell-এর final বের হয়ে গেছে কিনা; একবার pop করে process হলে True।
  • heap = [(grid[0][0], 0, 0)] — start cell, এ পর্যন্ত path-max = তার নিজের elevation; cost আগে রাখা জরুরি।
  • if (r, c) == (n-1, n-1): return t — destination প্রথমবার pop হলেই path-max final, return।
  • if visited[r][c]: continue — lazy deletion: stale heap entry বাদ (../shortest-path.md-এর trick)।
  • visited[r][c] = True — এই cell-এর সবচেয়ে ছোট path-max এখন প্রমাণিত।
  • max(t, grid[nr][nc]) — মূল মোচড়: নতুন path-cost = এ পর্যন্ত max আর neighbor-এর elevation-এর বড়টা।
  • heapq.heappush(...) — neighbor-কে নতুন cost সহ frontier-এ ঢোকাও (lazy: পুরোনো entry আলাদা করে মুছি না)।

17. Output walkthrough

swim_in_water([[0,2],[1,3]]): heap সবচেয়ে ছোট path-max আগে ছাড়ে। (0,0) থেকে (1,0) (1) আর (0,1) (2) frontier-এ আসে; দুটো পথেই destination (1,1)-এ পৌঁছাতে হলে elevation 3 cell পেরোতে হয়, তাই destination 3 নিয়ে pop হয় → return 3। বড় grid-এ সর্পিল পথ ধরে সবচেয়ে ছোট max হয় 16 → return 16। বাকি assert pass, শেষে print: সব test pass!।

18. Time complexity

O(n^2 · log n) — grid-এ n^2 টা cell, প্রতিটা heap-এ কয়েকবার push হতে পারে, প্রতিটা heap operation log(n^2) = O(log n)। edge সংখ্যা O(n^2) (প্রতি cell 4 neighbor) ধরে standard Dijkstra খরচ।

19. Space complexity

O(n^2) — visited array আর heap, দুটোতেই সর্বোচ্চ O(n^2) entry জমতে পারে।

20. Common mistakes

  • relax-এ max(t, elevation)-এর বদলে t + elevation বা step-পার্থক্য লেখা — এটা #20 নয়, এখানে cost cell-এর নিজের elevation-এর max।
  • (cost, r, c)-এর বদলে (r, c, cost) push করা — heap তখন row দিয়ে sort করে, ভুল।
  • start cell-এর cost 0 ধরা, grid[0][0] না নেওয়া — start উঁচু হলে ([[3,2],[0,1]]) উত্তর কম আসবে।
  • destination pop-এ return না করে পুরো heap চালানো — সঠিক হলেও অপ্রয়োজনীয়; first pop = final।
  • if visited[r][c]: continue বাদ দেওয়া — correctness টিকলেও stale entry re-expand হয়ে ধীর।

21. Which basic problem this inherits from

ভিত্তি: minimax Dijkstra (#20, Path With Minimum Effort; ../shortest-path.md)। আটকে গেলে আগে #20-এর কাঠামো মনে করো — heap-এ (cost, r, c), relax-এ max, destination first pop। এখানে শুধু cost-এর সংজ্ঞা আলাদা: step-পার্থক্যের বদলে cell-এর নিজের elevation। বাকি সব এক।

22. Similar harder problems

23. Pattern learned

Minimax Dijkstra (cell-cost variant): "ন্যূনতম সময়/থ্রেশহোল্ড যাতে একটা path খোলে" = path-এর max-কে minimize; Dijkstra-র relax-এ max(cost, cell) বসাও, destination first pop = answer। (পরে DSU দিয়েও solve করা যায়: elevation-ক্রমে cell যোগ করতে করতে কখন start-end এক component-এ আসে।)

24. Final summary

ভবিষ্যতের আমাকে: "Swim in Rising Water = minimax Dijkstra; cost = path-এর সর্বোচ্চ elevation, heap-এ (max_elev, r, c), relax max(t, grid[nr][nc]), destination first pop।" 'সবচেয়ে কম থ্রেশহোল্ড/সময় যাতে পথ খোলে' দেখলেই minimax Dijkstra (আর বিকল্পে DSU) মনে পড়বে। এরপর ../../10-disjoint-set-union/ শেষ করে এখানে DSU দিয়ে দ্বিতীয় solution লিখো।

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