কনটেন্টে যান

014 — Making A Large Island

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

Problem link ও উৎস

  • 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-ই এখানে আসল নায়ক

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

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

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

উদাহরণ
grid = [[1, 0],
        [0, 1]]

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

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

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

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

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

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

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

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

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

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

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

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

এখানে দুটো কাজ — (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 সরল।

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

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

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

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

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

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

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

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

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

ধাপ 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-এর দরকার নেই)।

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

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

ছবিতে বোঝা

ধাপ 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

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

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

  1. ধাপ 1: (0,0)=1; ডান (0,1)=0, নিচ (1,0)=0 → কোনো union নেই → island {0} size 1
  2. (1,1)=1; প্রতিবেশী সব 0 → island {3} size 1
  3. ধাপ 2, (0,1)=0: প্রতিবেশী বাঁ (0,0) root=0 size 1, নিচ (1,1) root=3 size 1 → distinct {0,3} → 1+1+1 = 3
  4. (1,0)=0: প্রতিবেশী উপর (0,0) root=0, ডান (1,1) root=3 → distinct {0,3} → 1+1+1 = 3
  5. best = 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 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!")

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

  • ধাপ 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 বেছে নেওয়া।

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

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

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

সময়

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

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

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

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

  • 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-এ নয়।

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

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

ভিত্তি: 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-র "বারো লাইন"-এ।

পরের অনুশীলন

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

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

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

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