015 — Swim in Rising Water (DSU variant)

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

• 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 হয়" খুঁজি

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

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

Input ও 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

চেনা উদাহরণে বোঝা

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

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

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

ভেতরের যুক্তি

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

কী দিয়ে তথ্য রাখব

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

এটি কেন উপযুক্ত

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

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

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

উদাহরণ

1) t-কে 0 থেকে grid-এর সর্বোচ্চ উচ্চতা পর্যন্ত এক করে বাড়াও:
2)    ≤t উচ্চতার cell দিয়ে grid-এ BFS করো
3)    goal ছুঁলে -> উত্তর t; থামো

কোথায় বেশি কাজ হচ্ছে

প্রতিটা 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 লাগে।

যে বিষয়টি খেয়াল করতে হবে

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

আরও কম কাজে সমাধান

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

ভাবনার পরিবর্তন

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

ছবিতে বোঝা

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

ছোট input-এ ধাপে ধাপে

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

কোড ও ব্যাখ্যা

Python

Python

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!")

কোডের প্রতিটি অংশ

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

Output মিলিয়ে দেখা

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

খরচ ও সাধারণ ভুল

সময়

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

অতিরিক্ত জায়গা

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

যে ভুলগুলো এড়াতে হবে

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

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

ভিত্তি: ../../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-তে।

পরের অনুশীলন

• Number of Islands II (streaming connectivity) — https://leetcode.com/problems/number-of-islands-ii/ (এই tracker-এর #13)
• Making A Large Island (component size) — https://leetcode.com/problems/making-a-large-island/ (#14)
• Path With Minimum Effort (একই minimax pattern) — https://leetcode.com/problems/path-with-minimum-effort/

কৌশলটি মনে রাখুন

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

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: "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।