কনটেন্টে যান

005 — Max Area of Island

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

Problem link ও উৎস

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

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

তোমাকে একটা m x n binary grid দেওয়া আছে — 1 মানে জমি, 0 মানে পানি। আগের মতোই একটা island হলো চার দিকে (উপর-নিচ-বাম-ডান) জুড়ে থাকা জমির cell-গুচ্ছ। প্রতিটা island-এর area মানে তার মধ্যে কতগুলো জমির cell। তোমাকে বলতে হবে সবচেয়ে বড় island-এর area কত। কোনো island না থাকলে উত্তর 0।

উদাহরণ
grid:
  0 1 0 0
  1 1 1 0
  0 0 1 1      <- দুটো island জোড়া লেগে আছে; সবচেয়ে বড়টার area = 6

Input ও output

উদাহরণ
Input : grid = [[0,1,0,0],[1,1,1,0],[0,0,1,1]]
Output: 6

Input : grid = [[1,0,1],[0,0,0],[1,1,0]]
Output: 2

Edge case (পুরো পানি): grid = [[0,0],[0,0]] -> 0

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

সমুদ্রের ছবিতে দ্বীপ গোনার সেই উদাহরণটাই, তবে এবার শুধু গুনছ না — প্রতিটা দ্বীপের জমির পরিমাণও মাপছ। কোনো দ্বীপে পা রাখলে পুরোটা হেঁটে ঘুরে আসো, প্রতি পা ফেলায় একটা করে টালি যোগ করো (আর দাগিয়ে রাখো যাতে দুবার না মাপো)। ঘোরা শেষে ওই দ্বীপের মোট টালি = তার area। সব দ্বীপের area মাপো, খাতায় সবচেয়ে বড়টা টুকে রাখো।

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

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

মূল ভিত হলো Number of Islands (#4)। ওখানে প্রতিটা island flood fill দিয়ে ডুবিয়ে শুধু কতগুলো island তা গুনতাম। এখানে ঠিক একই flood fill, কিন্তু ডুবানোর সময় কতগুলো cell ডুবল সেটাও গুনি — সেটাই ওই island-এর area। তারপর সব island-এর area-র মধ্যে maximum রাখি। গণনার কাজটা "কতবার শুরু হলো" থেকে বদলে "প্রতিবার কত বড় হলো" হয়ে গেল, ব্যস।

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

লুকানো logic: flood fill শুধু visited mark করে না, সে একটা সংখ্যাও ফেরত দিতে পারে — তার দখল করা cell-এর সংখ্যা। একটা island-এর area = সেই island-এর সব cell-এর যোগফল = flood fill চলাকালীন যতগুলো তাজা জমি ছোঁয়া হলো। প্রতিটা cell ঠিক একটা island-এর অন্তর্গত (component গুলো disjoint), তাই কোনো cell দুবার গোনা হয় না। মোট কাজ এখনো প্রতিটা cell একবার — শুধু সাথে একটা running max রাখা।

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

  • Grid নিজেই — implicit graph; neighbor হলো চার দিকের cell।
  • Visited চিহ্ন — in-place 1 → 0 করে ডুবানো, বা আলাদা visited 2D array।
  • Recursion stack (DFS) বা collections.deque (BFS) — এক island-এর সব cell explore করতে।
  • একটা integer — এ পর্যন্ত পাওয়া সবচেয়ে বড় area।

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

Grid-কে সরাসরি graph ধরা fit করে কারণ neighbor সম্পর্ক চার দিকেই fixed। in-place sinking fit করে কারণ একই cell দুবার গুনলে area ভুল হবে — ডুবানোই নিশ্চিত করে প্রতিটা cell একবার গোনা। DFS recursion fit করে কারণ area-টা স্বাভাবিকভাবেই recursion-এর return value হিসেবে যোগ হয়ে উপরে উঠে আসে (1 + চার দিকের area-র যোগফল); BFS-এ একটা counter বাড়াতে থাকলেই হয়।

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

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

প্রথম সরল চিন্তা: প্রতিটা জমির cell-এর জন্য আলাদা করে "এটা কোন island-এ আর সেই island কত বড়" বারবার নতুন করে হিসাব করা — যেমন প্রতিটা cell থেকে একটা পুরো নতুন traversal চালিয়ে তার component-এর size মাপা, এমনকি একই island-এর cell গুলোর জন্যও বারবার।

উদাহরণ
1) প্রতিটা cell (r,c) যেটা '1':
2)   (r,c) থেকে পুরো component traverse করে size মাপো
3)   global max আপডেট করো

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

কোনো visited memory ছাড়া একই island-এর প্রতিটা cell থেকে আলাদা traversal চালালে একই কাজ বহুবার হয় — একটা k-cell island-এর জন্য প্রায় k বার পুরো traversal, মোট খরচ component-প্রতি quadratic-এর দিকে যায়। অথচ একবার visited mark করে নিলে প্রতিটা cell সারা জীবনে একবারই ছোঁয়া হয় — পুরো grid-এর জন্য O(m·n)। মূল কথা: একটা island একবার মাপলেই হয়, প্রতিটা cell থেকে আবার মাপার দরকার নেই।

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

মূল observation: area হলো flood fill-এর return value। এক tweak — flood fill-কে দিয়ে শুধু mark করানো নয়, ডুবানো cell-এর সংখ্যাও ফেরত আনানো। প্রতিটা তাজা জমির cell থেকে এক flood = এক island-এর area; সবগুলোর মধ্যে সবচেয়ে বড়টা ধরে রাখো।

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

পুরো grid scan করো। তাজা জমির cell পেলে সেখান থেকে flood fill চালাও, যেটা ফেরত দেয় কতগুলো cell ডুবল (= এই island-এর area)। সেই area দিয়ে best = max(best, area) আপডেট করো। scan শেষে best-ই উত্তর। প্রতিটা cell scan-এ একবার, flood-এ বড়জোর একবার — O(m·n)। DFS-এ area = 1 + চার recursive call-এর যোগফল; BFS-এ pop করার সময় একটা counter বাড়াও।

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

মোচড়: "প্রতিটা cell-এর জন্য তার island কত বড় বারবার মাপব" না ভেবে ভাবো "flood fill-কেই বলে দিই কতগুলো cell ছুঁলে তা গুনে ফেরত দিতে — এক island, এক flood, এক area।" বারবার মাপা থেকে নেমে এসো একবারের mark-and-count-এ, আর শুধু সর্বোচ্চটা মনে রাখো।

ছবিতে বোঝা

grid = [[0,1,0,0],[1,1,1,0],[0,0,1,1]] দিয়ে দেখি:

উদাহরণ
grid:                 flood (1,1) থেকে, area গুনছি (* = এইমাত্র গোনা):
  0 1 0 0             0 * 0 0
  1 1 1 0     --->    * * * 0     ছোঁয়া cell: (0,1)(1,0)(1,1)(1,2)(2,2)(2,3)
  0 0 1 1             0 0 * *      area = 6

আর কোনো তাজা জমি নেই -> সবচেয়ে বড় area = 6

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

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

  1. best = 0। scan শুরু।
  2. (0,0) = 1, তাজা → flood: শুধু (0,0) (প্রতিবেশী সব 0/বাইরে), area = 1। best = max(0, 1) = 1।
  3. (0,1) = 0 এড়াও। (0,2) = 1, তাজা → flood: শুধু (0,2), area = 1। best = 1।
  4. row 1 সব 0। এড়াও।
  5. (2,0) = 1, তাজা → flood: (2,0) আর প্রতিবেশী (2,1)=1 ডুবল, area = 2। best = max(1, 2) = 2।
  6. (2,1) এখন ডুবে গেছে, (2,2) = 0। scan শেষ। return best = 2।

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

Python

Python
from collections import deque


def max_area_dfs(grid):
    if not grid or not grid[0]:
        return 0
    R, C = len(grid), len(grid[0])

    def flood(r, c):
        # বাইরে বা পানি/visited হলে এই দিকে 0 cell যোগ হয়
        if not (0 <= r < R and 0 <= c < C) or grid[r][c] != 1:
            return 0
        grid[r][c] = 0                        # ডুবিয়ে দেওয়াই visited-marking
        size = 1                              # নিজে একটা cell
        for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            size += flood(r + dr, c + dc)     # চার দিকের area যোগ হয়ে ওঠে
        return size

    best = 0
    for r in range(R):
        for c in range(C):
            if grid[r][c] == 1:               # তাজা জমি -> নতুন island
                best = max(best, flood(r, c))
    return best


def max_area_bfs(grid):
    # একই idea, queue দিয়ে (../../04-stack-and-queue/); area = pop করা cell-সংখ্যা
    if not grid or not grid[0]:
        return 0
    R, C = len(grid), len(grid[0])
    seen = [[False] * C for _ in range(R)]
    best = 0
    for sr in range(R):
        for sc in range(C):
            if grid[sr][sc] == 1 and not seen[sr][sc]:
                seen[sr][sc] = True           # push করার সময় mark করো
                q = deque([(sr, sc)])
                area = 0
                while q:
                    r, c = q.popleft()
                    area += 1                 # এই island-এ আরেকটা cell
                    for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                        nr, nc = r + dr, c + dc
                        if (0 <= nr < R and 0 <= nc < C
                                and grid[nr][nc] == 1 and not seen[nr][nc]):
                            seen[nr][nc] = True
                            q.append((nr, nc))
                best = max(best, area)
    return best


# ---- tests ----
g1 = [[0, 1, 0, 0], [1, 1, 1, 0], [0, 0, 1, 1]]
g2 = [[1, 0, 1], [0, 0, 0], [1, 1, 0]]
g3 = [[0, 0], [0, 0]]

assert max_area_bfs([row[:] for row in g1]) == 6
assert max_area_bfs([row[:] for row in g2]) == 2
assert max_area_bfs([row[:] for row in g3]) == 0
# DFS in-place grid বদলায়, তাই প্রতিবার copy পাঠাই
assert max_area_dfs([row[:] for row in g1]) == 6
assert max_area_dfs([row[:] for row in g2]) == 2
assert max_area_dfs([row[:] for row in g3]) == 0
print("সব test pass!")

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

  • if not grid or not grid[0]: return 0 — খালি grid-এ area নেই।
  • flood(r, c) — bounds বা পানি হলে 0 ফেরত; নাহলে cell ডুবিয়ে size = 1 ধরে চার দিকের flood-এর ফল যোগ করে।
  • size += flood(...) — recursion-এর সৌন্দর্য: প্রতিটা প্রতিবেশীর area নিচ থেকে যোগ হয়ে এই island-এর মোট area-তে জমা হয়।
  • grid[r][c] = 0 — ডুবানোটাই visited-marking; একই cell দুবার গোনা আটকায়।
  • best = max(best, flood(r, c)) — প্রতিটা island-এর area দিয়ে চলমান সর্বোচ্চ আপডেট।
  • BFS version-এ area += 1 pop করার সময় — প্রতিটা cell ঠিক একবার pop হয়, তাই গণনা সঠিক; seen mark q.append-এর পাশে।

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

max_area_dfs(g1): একমাত্র island (1,1) থেকে flood করে 6 cell গোনে → best = 6। g2-তে দুটো 1-cell island আর একটা 2-cell island → best = 2। g3 পুরো পানি → 0। BFS version-ও একই ফল। সব assert pass, শেষে print: সব test pass!।

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

সময়

O(m · n) — প্রতিটা cell scan-এ একবার আর flood/BFS-এ বড়জোর একবার ছোঁয়া হয়। max আপডেট O(1)।

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

O(m · n) worst case — DFS recursion stack এক লম্বা island বরাবর পুরো grid গভীরে যেতে পারে; BFS-এ queue ও seen array O(m·n)। শুধু একটা integer best বাড়তি।

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

  • flood fill-এ 1 যোগ না করে শুধু mark করা — তাহলে area সবসময় 0 বা ভুল।
  • visited mark করার আগে recurse করা — একই cell বারবার গোনা হয়ে area ফুলে যায় বা infinite loop।
  • প্রতিটা island-এর area ভুলে reset না করে আগেরটার সাথে যোগ করে ফেলা (BFS-এ area = 0 প্রতি island-এ নতুন করে)।
  • bounds check-এর আগে index করা — negative index চুপিচুপি wrap করে।

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

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

ভিত্তি: Number of Islands (#4) আর flood fill (#3)। #4 ছিল component গোনা; এই problem সেই একই flood fill-কে দিয়ে component-এর size মাপায়। এক ছোট tweak — mark করার সাথে count করা — আর একটা নতুন প্রশ্নের উত্তর বেরিয়ে আসে। পরের ধাপ: একই components idea কিন্তু grid-এর বদলে adjacency matrix input (#6)।

পরের অনুশীলন

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

Components + size counting: flood fill-কে শুধু visited-marker না বানিয়ে একটা counting tool বানাও — সে যত cell ছোঁয় ফেরত দিক, আর তুমি running max/sum রাখো। "সবচেয়ে বড় region", "region-এর size", "মোট জমি" — সব এই tweak-এর প্রয়োগ। খরচ এখনো O(m·n)।

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

ভবিষ্যতের আমাকে: "area = flood fill-এর return value; এক island, এক flood, এক count, আর সবচেয়ে বড়টা ধরে রাখো।" যখনই 'largest/size of region/component' দেখবে — flood fill চালাও কিন্তু এবার গুনতে গুনতে, আর max আপডেট করো; component গোনা (#4) আর মাপা (#5) একই reflex-এর দুই রূপ।

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