014 — Making A Large Island¶

Source¶

Original source: Grid component-size optimization exercise
Platform: LeetCode — https://leetcode.com/problems/making-a-large-island/
Topic: disjoint set union
Difficulty: Hard
Pattern: component sizes + best merge (একটা 0-কে 1 করে সবচেয়ে বড় island)
Basic idea inherited from: 10-এর size tracking — DSU-র size array-ই এখানে আসল নায়ক

1. Problem in simple words¶

n × n একটা grid, ঘরে 0 (জল) বা 1 (স্থল)। তোমাকে সর্বোচ্চ একটা 0-কে 1-এ বদলানোর সুযোগ দেওয়া হয়েছে (বদলাতে নাও পারো)। এর পরে সম্ভাব্য সবচেয়ে বড় island (পাশাপাশি 1-গুলোর connected group)-এর আকার কত হতে পারে — সেটা বের করো।

grid = [[1, 0],
        [0, 1]]

যেকোনো 0-কে 1 করলে দুটো আলাদা 1-island জোড়া যায় -> size 3
উত্তর = 3

2. Which basic idea does this inherit from?¶

ভিত্তি 10-এর size tracking — union by size রাখার সময় প্রতিটা root-এ তার component-এর আকার থাকে। #10-এ island গোনা শিখেছ; এখানে শুধু গোনা নয়, প্রতিটা island-এর আকার চাই, কারণ একটা 0 flip করলে চারপাশের island গুলোর আকার যোগ হয়।

3. What is the hidden math or logic?¶

লুকানো logic: একটা 0-cell flip করলে নতুন island-এর আকার = 1 + (তার চারপাশের distinct island-গুলোর আকারের যোগফল)। "distinct" শব্দটা গুরুত্বপূর্ণ — একই island যদি দুই প্রতিবেশী হয়ে আসে, তার আকার একবারই গোনা যাবে। DSU-র root দিয়ে distinct-ness ধরা যায়: একই root মানে একই island। তাই প্রতি 0-এর জন্য প্রতিবেশী root-গুলোকে একটা set-এ রেখে আকার যোগ করি।

4. Which data structure is needed?¶

একটা DSU (n·n element) যাতে প্রতিটা land-component-এর size থাকে, আর প্রতি 0-cell-এ distinct প্রতিবেশী root ধরতে একটা ছোট set। কোনো আলাদা graph লাগে না।

5. Why this data structure fits¶

এখানে দুটো কাজ — (1) সব 1-island-কে component-এ ভাগ করা ও তাদের আকার রাখা, (2) একটা 0-এর চারপাশের distinct island-আকার দ্রুত যোগ করা। DSU-র union ধাপ 1, আর find + size[root] ধাপ 2 — দুটোই O(α)। Traversal দিয়েও হয় (প্রতি island-কে id দিয়ে আকার map করে), কিন্তু DSU-তে size একদম built-in, তাই code সরল।

6. Real-life analogy¶

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

7. Visual explanation¶

ধাপ 1: সব 1 union করে island-এ ভাগ করো (root-এ size)। ধাপ 2: প্রতিটা 0-কে flip করে distinct প্রতিবেশী-size যোগ করো।

grid:           island label (root দিয়ে):
1 1 0           A A .
1 0 1     ->    A . B           island A size=3, island B size=1
0 0 1          . . B

0-cell flip করে দেখা:

(0,2) flip:  প্রতিবেশী -> উপরে নেই, নিচে B, বাঁয়ে A
             distinct {A,B} -> 1 + 3 + 1 = 5

(1,1) flip:  প্রতিবেশী -> উপরে A, নিচে কিছু না(0), বাঁয়ে A, ডানে B
             distinct {A,B} -> 1 + 3 + 1 = 5     <- best

সব 1 হলে (কোনো 0 নেই):  উত্তর = n*n

8. Example input and output¶

Input : grid=[[1,0],[0,1]]     Output: 3
Input : grid=[[1,1],[1,0]]     Output: 4   (একটা 0 flip -> পুরোটা এক)
Edge  : grid=[[1,1],[1,1]]  ->  কোনো 0 নেই  ->  n*n = 4
Edge  : grid=[[0,0],[0,0]]  ->  একটাই flip  ->  1

9. Brute force thinking¶

সরল চিন্তা: প্রতিটা 0-cell-কে একে একে 1 ধরো, প্রতিবার পুরো grid-এ DFS চালিয়ে সবচেয়ে বড় island গোনো, সেরা মান রাখো।

1) প্রতিটা 0-cell-এর জন্য:
2)    cell-কে temporarily 1 করো
3)    পুরো grid-এ DFS করে largest island গোনো
4)    cell-কে আবার 0 করো; best update করো

10. Why brute force is slow¶

প্রতিটা 0-cell-এর জন্য পুরো grid DFS — O((n²) · (n²)) = O(n⁴)। বড় grid-এ অসহনীয়, কারণ একই island-আকার বারবার গোনা হচ্ছে। DSU দিয়ে আকার গুলো একবার হিসেব করে রাখি; তারপর প্রতি 0-এ শুধু 4 প্রতিবেশীর root-size যোগ — পুরোটা O(n²)।

11. Key observation¶

মূল observation: island-আকার গুলো 0-flip-এর আগেই স্থির — প্রতিটা flip শুধু distinct প্রতিবেশী island গুলোকে সেতুবন্ধ করে। তাই আকার একবার precompute করো; প্রতিটা 0-এর উত্তর = 1 + চারপাশের distinct root-এর size-এর যোগ। distinct ধরতে set লাগবে, নইলে একই island দুবার গোনা হবে।

12. Optimized intuition¶

ধাপ 1: grid scan করে সব পাশাপাশি 1-cell union করো — root-এ size তৈরি। ধাপ 2: প্রতিটা 0-cell-এ 4 প্রতিবেশীর land-root গুলো set-এ রাখো, তাদের size যোগ + 1 → candidate; best রাখো। কোনো 0 না থাকলে উত্তর n·n (পুরো grid এক island, flip-এর দরকার নেই)।

13. Thinking tweak¶

মোচড়: "এই 0 flip করলে DFS করে দেখি কত বড় হলো" — এই বারবার-DFS ছাড়ো। বদলে আগে থেকেই প্রতিটা island-এর size জেনে রাখো; flip-এর প্রশ্ন তখন নেমে আসে "চারপাশে কোন কোন আলাদা island আছে, তাদের size যোগ করো"-তে। precompute + distinct-root যোগই চাবি।

14. Step-by-step dry run¶

Input grid=[[1,0],[0,1]], n=2, index r*2+c:

ধাপ 1: (0,0)=1; ডান (0,1)=0, নিচ (1,0)=0 → কোনো union নেই → island {0} size 1
(1,1)=1; প্রতিবেশী সব 0 → island {3} size 1
ধাপ 2, (0,1)=0: প্রতিবেশী বাঁ (0,0) root=0 size 1, নিচ (1,1) root=3 size 1 → distinct {0,3} → 1+1+1 = 3
(1,0)=0: প্রতিবেশী উপর (0,0) root=0, ডান (1,1) root=3 → distinct {0,3} → 1+1+1 = 3
best = 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 largest_island(grid):
    n = len(grid)
    dsu = DSU(n * n)
    # ধাপ 1: সব পাশাপাশি 1-cell union করো
    for r in range(n):
        for c in range(n):
            if grid[r][c] == 1:
                if r + 1 < n and grid[r + 1][c] == 1:
                    dsu.union(r * n + c, (r + 1) * n + c)
                if c + 1 < n and grid[r][c + 1] == 1:
                    dsu.union(r * n + c, r * n + c + 1)

    best = 0
    has_zero = False
    # ধাপ 2: প্রতিটা 0-কে flip করে চারপাশের distinct island size যোগ
    for r in range(n):
        for c in range(n):
            if grid[r][c] == 0:
                has_zero = True
                seen = set()
                total = 1                # নিজের flip-করা 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 grid[nr][nc] == 1:
                        root = dsu.find(nr * n + nc)
                        if root not in seen:
                            seen.add(root)
                            total += dsu.size[root]
                best = max(best, total)
    if not has_zero:                     # পুরো grid 1 — flip-এর দরকার নেই
        return n * n
    return best


# ---- tests ----
assert largest_island([[1, 0], [0, 1]]) == 3
assert largest_island([[1, 1], [1, 0]]) == 4
assert largest_island([[1, 1], [1, 1]]) == 4     # সব 1, কোনো 0 নেই
assert largest_island([[0, 0], [0, 0]]) == 1     # একটাই flip
print("সব test pass!")

16. Line-by-line code explanation¶

ধাপ 1 loop — শুধু ডান ও নিচ প্রতিবেশী দেখলেই যথেষ্ট; প্রতিটা edge একবার করে cover হয়, double-union এড়ানো যায়।
dsu.size[root] — union by size রাখায় root-এ component-এর আকার সরাসরি পাওয়া যায়।
seen = set() — একই island দুপাশে থাকলে তার size একবারই যোগ হয়; distinct-ness-এর গার্ড।
total = 1 — flip-করা cell নিজে গোনা হয়।
has_zero — যদি grid-এ একটাও 0 না থাকে, ধাপ 2-এ best 0 থেকে যেত; তখন সঠিক উত্তর পুরো grid n·n।
best = max(best, total) — সব 0-cell-এর মধ্যে সেরা flip বেছে নেওয়া।

17. Output walkthrough¶

test 1-এ দুটো বিচ্ছিন্ন 1-cell, মাঝের 0 flip করলে 3। test 2-এ একটাই 0; flip করলে চারপাশের 3 cell-এর island (size 3)-এর সাথে যোগ হয়ে 4। test 3-এ কোনো 0 নেই, has_zero False, উত্তর n·n=4। test 4-এ সব 0; যেকোনো একটা flip করলে আশেপাশে কোনো land নেই, total 1। শেষে print: সব test pass!।

18. Time complexity¶

O(n² · α(n²)) ≈ O(n²) — ধাপ 1-এ প্রতিটা cell-এ ধ্রুবসংখ্যক union, ধাপ 2-এ প্রতিটা 0-এ ≤4 find; প্রতিটা amortized near-constant।

19. Space complexity¶

O(n²) — DSU-র parent+size array; প্রতি 0-cell-এ seen set-এ বড়জোর 4টা root, তাই O(1) extra।

20. Common mistakes¶

distinct root গার্ড (seen) বাদ দেওয়া — একই island দুপাশে থাকলে size double-count হয়; classic bug।
"কোনো 0 নেই" case ভুলে যাওয়া — তখন best 0 ফেরত যায়, অথচ উত্তর n·n হওয়া উচিত।
ধাপ 1-এ চার দিক union করা (ডান+নিচ যথেষ্ট) — ভুল নয়, কিন্তু অপ্রয়োজনীয় double কাজ।
dsu.size[root]-এর বদলে dsu.size[nr*n+nc] ব্যবহার — size শুধু root-এ নির্ভরযোগ্য, non-root node-এ নয়।

21. Which basic problem this inherits from¶

ভিত্তি: 10-এর size tracking আর #10 grid DSU। #10-এ island গোনা; এখানে প্রতি island-এর size রেখে best-merge খোঁজা। ../../09-graphs/-এর island DFS দিয়েও size-map বানিয়ে করা যায়, কিন্তু DSU-তে size built-in বলে সরল। DSU snippet ../concept.md-র "বারো লাইন"-এ।

22. Similar harder problems¶

Number of Islands II (streaming connectivity) — https://leetcode.com/problems/number-of-islands-ii/ (এই tracker-এর #13)
Swim in Rising Water (threshold union) — https://leetcode.com/problems/swim-in-rising-water/ (#15)
Road Construction (live max component size) — CSES "Road Construction" (#17)

23. Pattern learned¶

Component sizes + best merge: যখন একটা পরিবর্তন (এখানে এক 0-flip) কয়েকটা component জুড়ে দেয় আর তুমি সেরা ফলাফল চাও, আগে DSU দিয়ে সব component-এর size precompute করো; তারপর প্রতিটা সম্ভাব্য merge-point-এ চারপাশের distinct root-গুলোর size যোগ করে best বেছে নাও। distinct-root set আর "no-change" edge case সবসময় খেয়াল রাখো।

24. Final summary¶

ভবিষ্যতের আমাকে: "একটা cell/edge বদলে সবচেয়ে বড় component কত?" দেখলে DSU-র size precompute ভাবো — বারবার DFS নয়। চারপাশের island একবারই গোনার জন্য distinct root-এর set রাখো, আর "সব already-1 / কোনো flip-যোগ্য জায়গা নেই" edge case আগে সামলে নাও।

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