005 — Max Area of Island

Source

• Original source: Classic grid components with size measurement
• Platform: LeetCode — https://leetcode.com/problems/max-area-of-island/
• Topic: graphs
• Difficulty: Medium
• Pattern: connected components + size counting (flood fill returns a count)
• Basic idea inherited from: Number of Islands (এই tracker-এর #4, 004-number-of-islands.md); flood fill (#3)

1. Problem in simple words

তোমাকে একটা 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

2. Which basic idea does this inherit from?

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

3. What is the hidden math or logic?

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

4. Which data structure is needed?

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

5. Why this data structure fits

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

6. Real-life analogy

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

7. Visual explanation

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

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

9. Brute force thinking

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

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

10. Why brute force is slow

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

11. Key observation

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

12. Optimized intuition

পুরো 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 বাড়াও।

13. Thinking tweak

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

14. Step-by-step dry run

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।

15. Python solution

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

16. Line-by-line code explanation

• 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-এর পাশে।

17. Output walkthrough

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

18. Time complexity

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

19. Space complexity

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

20. Common mistakes

• 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 করে।

21. Which basic problem this inherits from

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

22. Similar harder problems

• Number of Provinces (matrix input-এ component) — https://leetcode.com/problems/number-of-provinces/ (এই tracker-এর #6)
• Island Perimeter (size নয়, পরিধি) — https://leetcode.com/problems/island-perimeter/
• Number of Closed Islands (border-ছোঁয়া island বাদ) — https://leetcode.com/problems/number-of-closed-islands/

23. Pattern learned

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

24. Final summary

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