Skip to content

010 — Number of Islands (DSU variant)

Source

  • 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 গুনি

1. Problem in simple words

একটা 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

2. Which basic idea does this inherit from?

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

3. What is the hidden math or logic?

লুকানো 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 হয়ে যায়।

4. Which data structure is needed?

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

5. Why this data structure fits

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

6. Real-life analogy

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

7. Visual explanation

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

8. Example input and 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

9. Brute force thinking

সরল চিন্তা (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-সংখ্যা

10. Why brute force is slow

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

11. Key observation

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

12. Optimized intuition

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

13. Thinking tweak

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

14. Step-by-step dry run

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

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

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

16. Line-by-line code explanation

  • 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-সংখ্যা।

17. Output walkthrough

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

18. Time complexity

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

19. Space complexity

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

20. Common mistakes

  • চার দিক (উপর/নিচ/বাঁ/ডান) 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।

21. Which basic problem this inherits from

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

22. Similar harder problems

23. Pattern learned

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-তে নামে।

24. Final summary

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