010 — Number of Islands (DSU variant)¶

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

Problem link ও উৎস

Original source: Classic grid-connectivity exercise
Platform: LeetCode — https://leetcode.com/problems/number-of-islands/
Topic: disjoint set union
Difficulty: Medium
Pattern: grid cells as DSU elements
Basic idea inherited from: ../../09-graphs/-এর DFS version (ওখানে #4); এখানে grid cell-কে DSU node বানিয়ে component গুনি

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

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

একটা m × n grid দেওয়া, প্রতিটা cell '1' (land) বা '0' (water)। একটা island হলো পাশাপাশি (উপর/নিচ/বাঁ/ডান) যুক্ত land-cell-দের দল। তোমাকে island-এর মোট সংখ্যা গুনতে হবে।

উদাহরণ

grid =
  1 1 0 0 0
  1 1 0 0 0
  0 0 1 0 0
  0 0 0 1 1

উপরের-বাঁয়ের 1-গুলো এক island; মাঝের একা 1 আরেকটা; নিচের-ডানের জোড়া আরেকটা
                                                       ->  উত্তর: 3

Input ও output¶

উদাহরণ

Input :
  [["1","1","1","1","0"],
   ["1","1","0","1","0"],
   ["1","1","0","0","0"],
   ["0","0","0","0","0"]]
Output: 1

Input :
  [["1","1","0","0","0"],
   ["1","1","0","0","0"],
   ["0","0","1","0","0"],
   ["0","0","0","1","1"]]
Output: 3

Edge case (সব জল): [["0","0"],["0","0"]]  ->  0
Edge case (একটাই land): [["1"]]            ->  1

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

ভাবো একটা বিশাল ছকে আঁকা জমি, কিছু ঘর "শুকনো জমি" কিছু "জল"। প্রতিটা শুকনো ঘর শুরুতে নিজের একটা ছোট দ্বীপ। তুমি ডান আর নিচ বরাবর হাঁটো; দুটো শুকনো ঘর পাশাপাশি দেখলে তাদের দ্বীপ এক করে দাও (union)। সব হাঁটা শেষে যত আলাদা দ্বীপ টিকে থাকে, সেটাই উত্তর।

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

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

মূল ভিত হলো ../../09-graphs/-এর Number of Islands DFS (ওখানে #4) — সেখানে প্রতিটা না-দেখা land থেকে DFS চালিয়ে পুরো island "ডুবিয়ে" এসে গুনেছ। এখানে grid-কে graph হিসেবে দেখি যেখানে প্রতিটা land-cell একটা DSU node, আর পাশাপাশি land-cell দুটো union করি; island-সংখ্যা = land component-সংখ্যা।

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

লুকানো logic concept.md-র component count rule grid-এ প্রয়োগ: শুরুতে প্রতিটা land-cell আলাদা component ধরে land counter গুনি; পাশের দুই land merge হলে component একটা কমে। তাই island-সংখ্যা = (মোট land) − (সফল union)। 2D position-কে 1D index-এ map করার সূত্র: cell (r, c) → r * cols + c — তাহলেই grid একটা সাধারণ DSU হয়ে যায়।

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

একটা DSU rows × cols element-এর (প্রতিটা cell একটা সম্ভাব্য node), আর একটা land counter। শুধু land-cell গুনি, আর প্রতিটা land-cell-এর ডান ও নিচের প্রতিবেশী land হলে union করি।

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

প্রশ্নটা "কয়টা আলাদা land-দল?" — বিশুদ্ধ component counting, path নয়। DSU merge-only দুনিয়ায় grid cell-গুলো জুড়তে জুড়তে দল কমে — ঠিক যা দরকার। DFS-ও পারে, কিন্তু DSU streaming/online variant-এ (#13 Number of Islands II) সরাসরি বাড়ানো যায়, যা traversal পারে না — তাই grid-এ DSU শেখা মূল্যবান।

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

প্রথম সরল উপায়¶

সরল চিন্তা (09-graphs version): grid scan করো; প্রতিটা না-দেখা land-cell পেলে count বাড়াও আর DFS/BFS চালিয়ে পুরো island-টা '0' করে দাও (বা visited mark করো), যাতে আবার গোনা না হয়।

উদাহরণ

1) প্রতি cell ঘোরো
2) '1' আর না-দেখা হলে -> count += 1, DFS শুরু
3) DFS চারদিকের যুক্ত '1' সব visited করে দেয়
4) count = island-সংখ্যা

কোথায় বেশি কাজ হচ্ছে¶

DFS version O(m·n)-ই, কার্যত fast — DSU এখানে asymptotically দ্রুত নয়। আসল পার্থক্য নমনীয়তায়: DFS প্রতিবার পুরো island নতুন করে চষে, তাই cell একটা একটা করে যোগ হলে (streaming, #13) প্রতিবার পুরো traversal লাগে — অপচয়। DSU আগের merge মনে রাখে, তাই incremental update-এ স্বাভাবিক। Static একবারের গোনায় দুটোই সমান।

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

মূল observation: প্রতিটা cell-কে শুধু ডান আর নিচ প্রতিবেশীর সাথে union করলেই যথেষ্ট। চারদিক দেখার দরকার নেই — কারণ scan যখন এক cell-এ পৌঁছায়, তার বাঁ আর উপরের প্রতিবেশী আগেই process হয়ে গেছে আর তখন তারা এই cell-কে দেখেছিল। তাই অর্ধেক কাজে সব জোড়া একবার করেই ধরা পড়ে।

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

rows × cols-size DSU নাও আর land = 0। grid scan করো; প্রতিটা '1' cell-এ land += 1, তারপর তার ডান (r, c+1) আর নিচ (r+1, c) প্রতিবেশী যদি land হয়, union করো; সফল union-এ land -= 1। শেষে land-ই island-সংখ্যা। মোট O(m·n·α)।

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

মোচড়: "প্রতি island-এ DFS চালিয়ে ডুবিয়ে আসি" — এই traversal চিন্তার পাশে আরেকটা রাখো। ভাবো "প্রতিটা land প্রথমে একটা আলাদা দ্বীপ; পাশের দুই land পেলে দ্বীপ জোড়া লাগাই, counter কমাই।" cell = node, adjacency = union — grid-কে DSU-চোখে দেখাই চাবি (বিশেষত streaming variant-এর জন্য)।

ছবিতে বোঝা¶

land গুনতে গুনতে শুধু ডান ও নিচ প্রতিবেশীর সাথে union করো; প্রতি সফল merge-এ counter কমাও।

উদাহরণ

grid:  1 1 0
       1 0 0
       0 0 1     index = r*3 + c

land cells: (0,0)=0  (0,1)=1  (1,0)=3  (2,2)=8
শুরু: land = 4  (প্রতিটা land আলাদা)

cell (0,0)=land: ডান (0,1) land -> union(0,1) সফল -> land = 3
                 নিচ (1,0) land -> union(0,3) সফল -> land = 2
cell (0,1)=land: ডান (0,2) water -> skip
                 নিচ (1,1) water -> skip
cell (1,0)=land: ডান (1,1) water; নিচ (2,0) water -> skip
cell (2,2)=land: ডান নেই; নিচ নেই -> skip

ফল: components -> {(0,0),(0,1),(1,0)} আর {(2,2)} = 2 island

------ সব 0 হলে: কোনো land নেই -> land = 0 ------

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

Input [["1","1","0"],["0","1","0"],["0","0","1"]], cols=3 (cell গোনার পরপরই তার নিচ+ডান প্রতিবেশীর সাথে union হয়):

শুরু: land = 0
(0,0)='1' → land=1; নিচ(1,0)='0' skip; ডান(0,1)='1' → union(0,1) সফল → land=0
(0,1)='1' → land=1; নিচ(1,1)='1' → union(1,4) সফল → land=0; ডান(0,2)='0' skip
(1,1)='1' → land=1; নিচ(2,1)='0' skip; ডান(1,2)='0' skip
(2,2)='1' → land=1; কোনো প্রতিবেশী land নেই → final land = 2
দুই island: {(0,0),(0,1),(1,1)} আর {(2,2)} → return 2

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

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
        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 num_islands(grid):
    if not grid or not grid[0]:
        return 0
    rows, cols = len(grid), len(grid[0])
    dsu = DSU(rows * cols)               # প্রতিটা cell একটা সম্ভাব্য node
    land = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                land += 1                # নতুন land -> আপাতত আলাদা island
                idx = r * cols + c       # 2D -> 1D index
                if r + 1 < rows and grid[r + 1][c] == "1":   # নিচ প্রতিবেশী
                    if dsu.union(idx, (r + 1) * cols + c):
                        land -= 1        # merge হলো -> island একটা কমলো
                if c + 1 < cols and grid[r][c + 1] == "1":   # ডান প্রতিবেশী
                    if dsu.union(idx, r * cols + c + 1):
                        land -= 1
    return land


# ---- tests ----
assert num_islands([
    ["1", "1", "1", "1", "0"],
    ["1", "1", "0", "1", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "0", "0", "0"],
]) == 1
assert num_islands([
    ["1", "1", "0", "0", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "1", "0", "0"],
    ["0", "0", "0", "1", "1"],
]) == 3
assert num_islands([["0", "0"], ["0", "0"]]) == 0       # সব জল
assert num_islands([["1"]]) == 1                        # একটাই land
print("সব test pass!")

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

dsu = DSU(rows * cols) — প্রতিটা cell একটা সম্ভাব্য node, তাই DSU-র size cell-সংখ্যা।
land += 1 — নতুন land-cell পেলে প্রথমে আলাদা island ধরে নিই; merge হলে পরে কমবে।
idx = r * cols + c — 2D position-কে এক-মাত্রিক index-এ map; grid এতে সাধারণ DSU হয়ে যায়।
নিচ ও ডান প্রতিবেশী check — bound-এ থাকলে আর land হলে union; শুধু এই দুই দিক যথেষ্ট, কারণ বাঁ/উপর আগেই process হয়ে এই cell-কে দেখেছে।
if dsu.union(...): land -= 1 — সফল merge (দুই আলাদা component জোড়া) হলেই island একটা কমে; একই component হলে False, কিছু বদলায় না।
return land — টিকে থাকা land-component-সংখ্যাই island-সংখ্যা।

Output মিলিয়ে দেখা¶

প্রথম test-এ বাঁ-উপরের সব 1 ডান/নিচ union-এ এক component হয়ে যায় — 1 island। দ্বিতীয়টায় তিন আলাদা গুচ্ছ কখনো পাশাপাশি হয় না — 3 island। সব-জল case-এ একটাও land নেই, land থাকে 0। single-land case-এ একটা land, কোনো প্রতিবেশী নেই — 1। শেষে print: সব test pass!।

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

সময়¶

O(m · n · α(m·n)) ≈ O(m · n) — প্রতিটা cell একবার দেখা, প্রতিটায় বড়জোর দুটো union, প্রতিটা amortized near-constant। DFS version-ও O(m·n) — এখানে DSU asymptotically সমান।

অতিরিক্ত জায়গা¶

O(m · n) — parent + size array cell-সংখ্যার সমান। DFS-এর recursion stack-ও worst case O(m·n), তাই space-ও তুলনীয়।

যে ভুলগুলো এড়াতে হবে¶

চার দিক (উপর/নিচ/বাঁ/ডান) union করা — কাজ করে কিন্তু দ্বিগুণ; scan-order-এ শুধু নিচ আর ডান যথেষ্ট।
land += 1 করার পরে merge-এ land -= 1 করতে ভুলে যাওয়া — তখন প্রতিটা land আলাদা গোনা থেকে যায়, উত্তর বেশি আসে।
2D→1D index ভুল (r * rows + c লেখা r * cols + c-এর বদলে) — non-square grid-এ index ধাক্কা খায়।
bound check বাদ দেওয়া — শেষ row/column-এ index out-of-range।

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

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

ভিত্তি: ../../09-graphs/-এর Number of Islands DFS (ওখানে #4) — সেখানে island ডুবিয়ে গুনেছ, এখানে cell union করে component গুনছ। DSU-vs-traversal: static একবারের গোনায় দুটোই O(m·n), DFS তর্কসাপেক্ষে simpler; কিন্তু cell একটা একটা করে যোগ হলে (streaming) DFS প্রতিবার পুরো traversal চায়, DSU আগের merge মনে রাখে — সেখানেই DSU জেতে (#13 Number of Islands II দেখো)।

পরের অনুশীলন¶

Number of Islands II (cell streaming যোগ — যেটা traversal ভালো পারে না) — https://leetcode.com/problems/number-of-islands-ii/ (এই tracker-এর #13)
Making A Large Island (component size + best merge) — https://leetcode.com/problems/making-a-large-island/ (#14)
Most Stones Removed (grid-ঘেঁষা creative union) — https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/ (#11)

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

Grid cells as DSU elements: cell (r,c)-কে r*cols + c দিয়ে 1D node বানাও; পাশের land-cell দুটো union করো (scan-order-এ শুধু নিচ+ডান); component-সংখ্যাই উত্তর। যেকোনো grid-connectivity problem এই 2D→1D mapping দিয়ে সাধারণ DSU-তে নামে।

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

ভবিষ্যতের আমাকে: grid-এ "কয়টা যুক্ত অঞ্চল?" দেখলে DFS-ই প্রথম পছন্দ (static হলে); কিন্তু DSU-চোখটাও রাখো — cell = node (r*cols+c), পাশের land = union, component-সংখ্যা = উত্তর। cell একটা একটা করে এলে DSU-ই একমাত্র স্বাভাবিক পথ — তাই এই mapping রপ্ত রাখো।

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