013 — Number of Islands II

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

Problem link ও উৎস

• Original source: Streaming dynamic-connectivity exercise
• Platform: LeetCode — https://leetcode.com/problems/number-of-islands-ii/
• Topic: disjoint set union
• Difficulty: Hard
• Pattern: streaming dynamic connectivity (প্রতিটা addition-এর পর live island count)
• Basic idea inherited from: 10-এর grid DSU (#10 Number of Islands) — যে problem traversal স্বাভাবিকভাবে পারে না, কারণ land একটা একটা করে যোগ হতে থাকে

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

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

m × n একটা grid শুরুতে পুরো জল (সব 0)। তারপর একগুচ্ছ position = (row, col) আসে — প্রতিবার ওই ঘর জলে থেকে স্থলে (land) বদলায়। প্রতিটা addition-এর ঠিক পরে বলতে হবে এই মুহূর্তে কতগুলো আলাদা island আছে। উত্তর একটা list — প্রতিটা addition-এর জন্য একটা সংখ্যা।

উদাহরণ

m=3, n=3, positions = [(0,0),(0,1),(1,2),(2,1)]

(0,0) যোগ -> 1 island
(0,1) যোগ -> (0,0)-র পাশে, merge -> 1 island
(1,2) যোগ -> আলাদা -> 2 islands
(2,1) যোগ -> আলাদা -> 3 islands

answer = [1, 1, 2, 3]

Input ও output

উদাহরণ

Input : m=3, n=3, positions=[[0,0],[0,1],[1,2],[2,1]]   Output: [1,1,2,3]
Input : m=2, n=2, positions=[[0,0],[1,1],[0,1]]         Output: [1,2,1]
Edge  : m=3, n=3, positions=[[0,0],[0,0]]  ->  duplicate add  ->  [1,1]

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

ভাবো সমুদ্রের মধ্যে তুমি একটা একটা করে পাথর ফেলে জমি বানাচ্ছ। নতুন পাথর ফেললে প্রথমে সেটা একটা নতুন ছোট্ট দ্বীপ। কিন্তু যদি সে আগের কোনো দ্বীপের গায়ে লাগে, দুটো মিশে এক দ্বীপ হয়; দুপাশে দুটো আলাদা দ্বীপ থাকলে একটা পাথর সেতু হয়ে তিনটে দ্বীপকে এক করেও দিতে পারে। প্রতিটা পাথরের পর তুমি গুনছ — এখন কয়টা দ্বীপ। merge শুধু কমায়, নতুন পাথর শুধু সম্ভাব্য বাড়ায়।

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

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

ভিত্তি #10 (Number of Islands DSU) — grid-cell-কে DSU node বানানো আর পাশাপাশি land union করা। কিন্তু #10-এ পুরো grid একবারে দেওয়া থাকত, তাই একটা DFS-ই যথেষ্ট ছিল। এখানে land স্রোতের মতো আসে আর মাঝে মাঝে count জানতে চাওয়া হয় — এটাই dynamic connectivity, যেখানে DSU traversal-কে হারিয়ে দেয়।

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

লুকানো logic সেই component-count invariant: নতুন একটা land যোগ করলে ধরে নাও সে নিজেই একটা নতুন island (count += 1)। তারপর তার 4 প্রতিবেশীর প্রতিটা ইতিমধ্যে-land cell-এর সাথে union করো; প্রতিটা সফল union মানে দুটো আলাদা island এক হলো (count -= 1)। একই প্রতিবেশী-component দুবার merge হবে না, কারণ দ্বিতীয়বার union False ফেরাবে।

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

একটা DSU (m·n element) + একটা is_land boolean grid যাতে জানা যায় কোন cell এখন land। কোনো adjacency list নেই; প্রতিবেশী সম্পর্ক grid-এর geometry থেকেই আসে।

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

প্রশ্ন "এই মুহূর্তে কয়টা island?" — অর্থাৎ live component count, যা addition-এর মাঝে মনে রাখতে হবে। DSU ঠিক তাই করে: union-এর মাঝে state ধরে রাখে, প্রতিটা addition O(α)-তে। Traversal হলে প্রতিটা addition-এর পর পুরো grid নতুন করে scan করতে হতো — O(k · m · n), যেখানে k = addition সংখ্যা; অপচয়।

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

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

সরল চিন্তা: প্রতিটা addition-এর পর পুরো current grid-এ DFS/BFS দিয়ে island গোনো।

উদাহরণ

1) position অনুযায়ী cell-কে land করো
2) পুরো grid scan করে unvisited land থেকে DFS চালাও
3) যতবার নতুন DFS শুরু হলো = island সংখ্যা; list-এ যোগ করো

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

প্রতিটা addition-এর জন্য পুরো grid পুনরায় চষা — O(m · n) প্রতি addition, মোট O(k · m · n)। বড় grid আর হাজারো addition-এ এটা প্রচুর redundant কাজ, কারণ একটা মাত্র নতুন cell যোগ হওয়ায় island সংখ্যা শুধু +1 বা সামান্য কমে — পুরো grid নতুন করে গোনার দরকারই নেই। DSU প্রতিটা addition কেবল 4 প্রতিবেশী দেখে O(α)-তে সারে। এটাই সেই classic case যেখানে streaming বলেই DSU traversal-কে হারায়।

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

মূল observation: নতুন land = ধরে নাও +1 island, তারপর যত আলাদা প্রতিবেশী-component-এ সে জোড়ে তত -1। Island সংখ্যার বদল সম্পূর্ণভাবে local — শুধু এই cell আর তার 4 প্রতিবেশীর উপর নির্ভর করে। আর duplicate addition (একই cell দুবার) island সংখ্যা বদলায় না, তাই আগেই গার্ড দিতে হবে।

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

is_land grid খালি রাখো, count = 0। প্রতিটা position-এ: যদি cell আগেই land হয় তবে count অপরিবর্তিত রেখে current count append করো; নইলে cell-কে land করো, count += 1, তারপর 4 প্রতিবেশীর প্রতিটা land cell-এর সাথে union — সফল হলে count -= 1। শেষে current count append। প্রতিটা addition amortized O(α)।

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

মোচড়: "পুরো grid-এ এখন কয়টা island?" — পুরোটা নতুন করে গোনা ছাড়ো। বদলে জিজ্ঞেস করো "এই একটা নতুন cell island সংখ্যা কতটা বদলাল?" উত্তর সবসময় local: +1 minus (যত আলাদা প্রতিবেশী-island সে জোড়ে)। Global recount-কে local delta-তে নামানোই চাবি।

ছবিতে বোঝা

প্রতিটা addition: count += 1, তারপর প্রতিটা land প্রতিবেশীর সাথে union; সফল union-এ count -= 1।

উদাহরণ

m=3, n=3 — '.' জল, '#' land,  index = r*n + c

(0,0) যোগ:        (0,1) যোগ:        (1,2) যোগ:        (2,1) যোগ:
 # . .            # # . . .         # # .            # # .
 . . .            . . .             . . #            . . #
 . . .            . . .             . . .            . # .

count: 0->1       1, পাশে merge     1 ->2  (আলাদা)    2 ->3  (আলাদা)
       (নতুন)         -> 1                 (নতুন)            (নতুন)

answer = [1, 1, 2, 3]

মাঝের পাথর সেতু-case (2x2):
positions = [(0,0),(1,1),(0,1)]
 # .            # .            # #
 . .   ->1      . #   ->2      . #   -> (0,1) দুপাশে merge -> 1
answer = [1, 2, 1]

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

Input m=3, n=3, positions=[[0,0],[0,1],[1,2],[2,1]], index r*3+c:

1. (0,0): নতুন; count 0→1; প্রতিবেশী সব জল, union নেই → append 1
2. (0,1): নতুন; count 1→2; বাঁ প্রতিবেশী (0,0) land; union সফল → count 2→1 → append 1
3. (1,2): নতুন; count 1→2; চার প্রতিবেশী সব জল → append 2
4. (2,1): নতুন; count 2→3; চার প্রতিবেশী সব জল → append 3
5. result = [1, 1, 2, 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 num_islands2(m, n, positions):
    dsu = DSU(m * n)
    is_land = [[False] * n for _ in range(m)]
    count = 0
    res = []
    for r, c in positions:
        if is_land[r][c]:                # duplicate add — count বদলায় না
            res.append(count)
            continue
        is_land[r][c] = True
        count += 1                       # নতুন island ধরে নাও
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and is_land[nr][nc]:
                if dsu.union(r * n + c, nr * n + nc):
                    count -= 1           # সফল merge -> এক island কমলো
        res.append(count)
    return res


# ---- tests ----
assert num_islands2(3, 3, [[0, 0], [0, 1], [1, 2], [2, 1]]) == [1, 1, 2, 3]
assert num_islands2(1, 1, [[0, 0]]) == [1]
assert num_islands2(3, 3, [[0, 0], [0, 1], [0, 2], [1, 2]]) == [1, 1, 1, 1]
assert num_islands2(2, 2, [[0, 0], [1, 1], [0, 1]]) == [1, 2, 1]   # মাঝের cell দুই দ্বীপ জোড়ে
assert num_islands2(3, 3, [[0, 0], [0, 0]]) == [1, 1]              # duplicate add
print("সব test pass!")

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

• is_land — boolean grid; কোন cell এখন land তা জানায়, যাতে শুধু land প্রতিবেশীর সাথেই union করি।
• if is_land[r][c]: ... continue — duplicate addition গার্ড; island সংখ্যা বদলায় না, শুধু আগের count আবার লিখি।
• count += 1 — নতুন land প্রথমে নিজে একটা island ধরা হয়।
• চার (dr, dc) loop — 4-direction প্রতিবেশী; bound check করে শুধু land প্রতিবেশীর সাথে union।
• if dsu.union(...): count -= 1 — সফল merge মানেই দুটো আলাদা island এক হলো; একই component দুবার merge হবে না (False ফেরে), তাই over-counting নেই।
• res.append(count) — প্রতিটা addition-এর পর live island সংখ্যা list-এ।

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

test 1-এ ধাপে ধাপে [1,1,2,3] — দ্বিতীয় cell merge করায় count 2 থেকে 1-এ নামে। test 2-এ একটাই cell, 1। test 3-এ একই row-এ সব land পরপর merge হয়, count সবসময় 1। test 4-এ (0,1) দুপাশের (0,0) ও (1,1)-কে merge করে 2→1, তাই [1,2,1]। test 5-এ একই cell দুবার, count অপরিবর্তিত [1,1]। শেষে print: সব test pass!।

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

সময়

O(k · α(m·n)) ≈ O(k) — k = addition সংখ্যা; প্রতিটা addition ধ্রুবসংখ্যক (≤4) union/find, প্রতিটা amortized near-constant। Grid initialize ধরলে O(m·n + k)।

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

O(m·n) — DSU-র parent+size array আর is_land grid; output list O(k)।

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

• duplicate addition গার্ড না দেওয়া — একই cell দুবার এলে count ভুল বাড়ে/কমে।
• count += 1 ভুলে যাওয়া, বা প্রতিবেশী merge-এ count -= 1 শুধু সফল union-এ না করে প্রতিটা land প্রতিবেশীতেই করা (over-count)।
• index flatten-এ r * n + c-র বদলে r * m + c লেখা (column সংখ্যা n, তাই গুণ n দিয়ে)।
• traversal দিয়ে সমাধানের চেষ্টা — সঠিক হলেও streaming-এ ধীর; এটাই DSU দেখানোর জায়গা (cross-ref ../../09-graphs/)।

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

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

ভিত্তি: 10-এর #10 Number of Islands (grid DSU) আর ../../09-graphs/-এর island DFS। static grid-এ DFS সমান ভালো; কিন্তু land একটা একটা করে যোগ হলে DFS প্রতিবার পুরো grid চষে, DSU শুধু delta হিসেব করে। এই পার্থক্যটাই দেখায় কখন DSU বেছে নিতে হয়। DSU snippet ../concept.md-র "বারো লাইন"-এ।

পরের অনুশীলন

• Making A Large Island (offline flip + component size) — https://leetcode.com/problems/making-a-large-island/ (এই tracker-এর #14)
• Swim in Rising Water (threshold union) — https://leetcode.com/problems/swim-in-rising-water/ (#15)
• Road Construction (live component count, CP scale) — CSES "Road Construction" (#17)

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

Streaming dynamic connectivity: যখন element একটা একটা করে যোগ হয় আর প্রতিটা addition-এর পর component/count জানতে চাওয়া হয়, DSU দিয়ে state ধরে রাখো; প্রতিটা addition-এ "+1 ধরো, যত merge তত -1" দিয়ে count update করো। এটাই DSU vs traversal-এর নির্ণায়ক জায়গা — traversal প্রতিবার শূন্য থেকে গোনে, DSU মনে রাখে।

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

ভবিষ্যতের আমাকে: "after each addition / right now কয়টা component?" শুনলেই DSU ধরো — এটা traversal-এর দুর্বল জায়গা। নতুন cell-এর delta সবসময় local: +1 minus distinct-neighbor-merges। duplicate গার্ড আর সফল-union-এ-only-decrement — এই দুটো ঠিক রাখলে Hard হলেও পরিষ্কার।

---

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