Skip to content

015 — Swim in Rising Water (DSU variant)

Source

  • Original source: Threshold-connectivity / Kruskal-style exercise
  • Platform: LeetCode — https://leetcode.com/problems/swim-in-rising-water/
  • Topic: disjoint set union
  • Difficulty: Hard
  • Pattern: Kruskal-style threshold union (height order-এ cell union, start ও goal কখন যুক্ত)
  • Basic idea inherited from: ../../09-graphs/-এর Dijkstra version (ওখানে #25); এখানে আমরা shortest path নয়, "কোন threshold-এ দুই কোণ connect হয়" খুঁজি

1. Problem in simple words

n × n একটা grid, প্রতিটা ঘরে একটা উচ্চতা grid[r][c] (সব মান আলাদা, 0 থেকে n²−1)। সময় t-তে জলস্তর t; কোনো ঘরে যাওয়া যায় শুধু যদি ঘরের উচ্চতা ≤ t। উপর-বাঁ কোণ (0,0) থেকে নিচ-ডান কোণ (n−1,n−1)-এ পৌঁছাতে সর্বনিম্ন কত সময় লাগবে — সেটা বের করো।

grid = [[0, 2],
        [1, 3]]

t=3 হলে চারটে ঘরই ডোবে, (0,0)->(1,1) পথ খোলে
উত্তর = 3

2. Which basic idea does this inherit from?

ভিত্তি ../../09-graphs/-এর Dijkstra/shortest-path চিন্তা (ওখানে #25) — সেখানে তুমি minimax path (পথের সর্বোচ্চ উচ্চতা minimize) Dijkstra/heap দিয়ে বের করেছ। এখানে একই উত্তর DSU-র Kruskal-style দৃষ্টিতে: cell গুলোকে উচ্চতা-ক্রমে "খুলতে" থাকো; যে মুহূর্তে start ও goal এক component-এ পড়ে, সেই উচ্চতাই উত্তর।

3. What is the hidden math or logic?

লুকানো logic: উত্তরটা হলো bottleneck/minimax — start থেকে goal-এ যাওয়ার যেকোনো পথের সর্বোচ্চ উচ্চতা গুলোর মধ্যে সবচেয়ে ছোটটা। জলস্তর t বাড়ালে কেবল নতুন cell খোলে (merge-only)। তাই cell গুলো উচ্চতা ascending-এ একে একে খুলে union করতে থাকলে, যেই মুহূর্তে find(start) == find(goal), সেই cell-এর উচ্চতাই হলো ন্যূনতম threshold।

4. Which data structure is needed?

একটা DSU (n·n element) + cell-গুলোকে উচ্চতা-ক্রমে সাজানো একটা order, আর একটা opened boolean যাতে শুধু ইতিমধ্যে-খোলা প্রতিবেশীর সাথে union করি। কোনো heap লাগে না (Dijkstra version-এ লাগত)।

5. Why this data structure fits

জলস্তর বাড়া = monotonic, কেবল cell যোগ হয়, কখনো বন্ধ হয় না — merge-only দুনিয়া, DSU-র আদর্শ ক্ষেত্র। প্রশ্নটা "কখন দুই কোণ একই component-এ?" — DSU-র জন্মগত কাজ। প্রতিটা cell একবার খোলে, ≤4 union; পুরোটা প্রায় linear (sort বাদ দিলে)।

6. Real-life analogy

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

7. Visual explanation

cell-গুলো উচ্চতা ascending-এ খোলো; খোলার পর খোলা প্রতিবেশীর সাথে union; start ও goal এক হলে থামো।

grid:                উচ্চতা ascending ক্রম:
0 2                  0 -> 1 -> 2 -> 3
1 3                  (0,0)(1,0)(0,1)(1,1)

খোলা (#) ক্রমে union:

t=0: # .      t=1: # .      t=2: # #      t=3: # #
     . .           # .           # .           # #
start root         (0,0)~(1,0)   (0,1) যোগ      (1,1) যোগ ->
goal এখনো আলাদা    এখনো আলাদা    এখনো আলাদা     start~goal এক!  -> 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  : grid=[[0]]  ->  শুধু এক cell, start==goal  ->  0

9. Brute force thinking

সরল চিন্তা: প্রতিটা সম্ভাব্য সময় t = 0..n²−1-এর জন্য পরীক্ষা করো — ওই t-তে ≤t উচ্চতার cell দিয়ে (0,0) থেকে (n−1,n−1)-এ BFS/DFS করে path আছে কি না; প্রথম যে t-তে path খোলে সেটাই উত্তর।

1) t = 0,1,2,...:
2)    ≤t উচ্চতার cell দিয়ে grid-এ BFS করো
3)    goal ছুঁলে -> উত্তর t; থামো

10. Why brute force is slow

প্রতিটা t-এর জন্য পুরো grid BFS — O(n² · n²) = O(n⁴) worst case (binary search দিলে O(n² log n) নামে, কিন্তু তবু প্রতি ধাপে পুরো BFS)। DSU version cell-গুলো একবারই উচ্চতা-ক্রমে process করে, প্রতিটা ≤4 union — sort বাদে প্রায় linear। Dijkstra version-ও দ্রুত (O(n² log n)), কিন্তু DSU-তে heap-এর বদলে শুধু একটা sorted order লাগে।

11. Key observation

মূল observation: উত্তর = সেই ন্যূনতম উচ্চতা, যেখানে start ও goal এক component-এ পড়ে। যেহেতু জলস্তর বাড়লে কেবল cell যোগ হয় (কখনো বাদ যায় না), cell গুলো ascending উচ্চতায় union করতে থাকলে প্রথম যে union start ও goal-কে মেলায়, তার উচ্চতাই minimax উত্তর।

12. Optimized intuition

সব cell-কে উচ্চতা ascending-এ sort করো। একে একে cell "খোলো"; প্রতিটা খোলার পর তার যেসব প্রতিবেশী ইতিমধ্যে খোলা তাদের সাথে union করো। প্রতিটা union-এর পর check করো find(start) == find(goal) — হলে এই cell-এর উচ্চতাই উত্তর, থামো। (এটাই Kruskal-এর "edge ascending, union, connect হলে থামো"-র grid রূপ।)

13. Thinking tweak

মোচড়: "প্রতিটা t-এ আবার path খুঁজি" — এই বারবার-search ছাড়ো। বদলে cell-গুলোকে উচ্চতার ক্রমে একবার খুলতে থাকো আর জিজ্ঞেস করো "এই cell খোলায় কি start ও goal এক হলো?" path-search-কে incremental union-এ অনুবাদ করাই চাবি — ঠিক Kruskal যেভাবে edge sort করে union করে।

14. Step-by-step dry run

Input grid=[[0,2],[1,3]], n=2, ascending ক্রম উচ্চতা 0,1,2,3 = cell (0,0),(1,0),(0,1),(1,1); start=0, goal=3:

  1. উচ্চতা 0 → (0,0) খোলো; খোলা প্রতিবেশী নেই; find(0)≠find(3)
  2. উচ্চতা 1 → (1,0) খোলো; উপর (0,0) খোলা → union(2,0); start/goal এখনো আলাদা
  3. উচ্চতা 2 → (0,1) খোলো; বাঁ (0,0) খোলা → union(1,0); এখনো আলাদা
  4. উচ্চতা 3 → (1,1) খোলো; উপর (0,1) খোলা → union(3,1), বাঁ (1,0) খোলা → union(3,2); এখন find(0)==find(3) → উত্তর 3

15. Python solution

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))     # প্রথমে সবাই নিজের নিজের root
        self.size = [1] * n              # প্রতিটা group-এ একজন

    def find(self, x):                   # representative + path compression
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # path halving
            x = self.parent[x]
        return x

    def union(self, x, y):               # union by size; merge হলে True
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False                 # আগে থেকেই এক group
        if self.size[rx] < self.size[ry]:
            rx, ry = ry, rx              # rx এখন বড় root
        self.parent[ry] = rx            # ছোটটা বড়টার নিচে ঝোলে
        self.size[rx] += self.size[ry]
        return True


def swim_in_water(grid):
    n = len(grid)
    dsu = DSU(n * n)
    # cell-গুলো উচ্চতা ascending-এ "খুলবে" (Kruskal-style order)
    order = sorted(range(n * n), key=lambda i: grid[i // n][i % n])
    opened = [False] * (n * n)
    start, goal = 0, n * n - 1
    for i in order:
        r, c = i // n, i % n
        opened[i] = True                 # time = grid[r][c]-এ এই cell ডোবে
        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 opened[nr * n + nc]:
                dsu.union(i, nr * n + nc)
        if dsu.find(start) == dsu.find(goal):
            return grid[r][c]            # যে উচ্চতায় start ও goal connect হলো
    return grid[goal // n][goal % n]      # fallback (n==1 case)


# ---- 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          # শুধু এক cell
print("সব test pass!")

16. Line-by-line code explanation

  • order = sorted(...) — সব cell-index উচ্চতা ascending-এ; এটাই Kruskal-এর "edge sorted by weight"-র grid analog।
  • opened — কোন cell এ-পর্যন্ত খোলা; শুধু খোলা প্রতিবেশীর সাথেই union করি, যাতে threshold সঠিক থাকে।
  • opened[i] = True — উচ্চতা grid[r][c]-তে এই cell ডোবে / খোলে।
  • চার (dr,dc) loop — খোলা প্রতিবেশীর সাথে union; নতুন খোলা cell বিদ্যমান component-এ জোড়ে।
  • if dsu.find(start) == dsu.find(goal) — start ও goal এক component-এ পড়লেই থামো; এই cell-এর উচ্চতাই minimax উত্তর।
  • শেষ return — n==1-এ loop-এর ভেতরের check প্রথম cell-এই True, তবু safety fallback।

17. Output walkthrough

test 1-এ উচ্চতা 3-এর cell খোলায় দুই কোণ মেলে, উত্তর 3। test 2-এ বড় spiral grid-এ 16 উচ্চতায় প্রথমবার দুই কোণ একই জলরাশিতে আসে। test 3-এ একটাই cell, start==goal, উচ্চতা 0। শেষে print: সব test pass!।

18. Time complexity

O(n² log n + n² · α(n²)) ≈ O(n² log n) — sort-ই dominant (n² cell), তারপর প্রতিটা cell-এ ধ্রুবসংখ্যক union/find amortized near-constant। Dijkstra version-ও O(n² log n)।

19. Space complexity

O(n²) — DSU array, order list, আর opened boolean grid।

20. Common mistakes

  • খোলা না-হওয়া প্রতিবেশীর সাথেও union করা — তখন threshold আগেভাগে মিলে ভুল (ছোট) উত্তর আসে; শুধু opened প্রতিবেশী।
  • start/goal connect check প্রতিটা cell খোলার পর না করে loop শেষে করা — তাহলে সঠিক প্রথম threshold মিস।
  • উত্তর হিসেবে loop-counter/সময়ের index না দিয়ে grid[r][c] (আসল উচ্চতা) দিতে ভুলে যাওয়া।
  • n==1 edge case ভুলে যাওয়া — যদিও এখানে প্রথম cell-এই start==goal ধরা পড়ে।

21. Which basic problem this inherits from

ভিত্তি: ../../09-graphs/-এর Dijkstra/minimax (#25)। সেই একই উত্তর এখানে Kruskal-style DSU দিয়ে — heap-এর বদলে sorted order, relax-এর বদলে union। দুটোই O(n² log n), কিন্তু DSU version "threshold-এ connectivity"-র সবচেয়ে পরিষ্কার রূপ। DSU snippet ../concept.md-র "বারো লাইন"-এ; Kruskal-connection ../concept.md-র Pattern C-তে।

22. Similar harder problems

23. Pattern learned

Kruskal-style threshold union: যখন প্রশ্ন "কোন ন্যূনতম threshold-এ দুই বিন্দু connect হয়" (minimax/bottleneck path), তখন edge/cell গুলোকে weight/উচ্চতা ascending-এ sort করো আর একে একে union করতে থাকো; প্রথম যে union দুই বিন্দুকে মেলায়, তার weight-ই উত্তর। heap-Dijkstra-র বদলে sort-then-union — একই ফল, প্রায়ই সরল।

24. Final summary

ভবিষ্যতের আমাকে: "minimax / bottleneck / কোন threshold-এ connect" দেখলে দুটো রাস্তা মনে রাখো — Dijkstra-minimax (heap) বা Kruskal-DSU (sort+union)। DSU রাস্তায় cell/edge ascending-এ খোলো, প্রতিবার "start ও goal কি এক হলো?" check করো; merge-only বলেই DSU এখানে স্বাভাবিক fit।

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