008 — Number of Islands¶

Source¶

Original source: Classic capstone interview problem (grid flood fill)
Platform: LeetCode — https://leetcode.com/problems/number-of-islands/
Topic: graphs + recursion (DFS)
Difficulty: Medium
Pattern: Grid flood fill — connected-component counting via DFS
Basic idea inherited from: এটা একটা cross-topic capstone — এখানে মেশে 09 graphs (grid-টাকে একটা implicit graph ধরা: প্রতিটা land cell একটা node, পাশের land cell-এর সাথে edge; connected component গোনা) আর 06 recursion (DFS দিয়ে একটা cell থেকে শুরু করে পুরো island ছেয়ে ফেলা — flood fill)। দুই tool জোড়া লাগলেই এই problem।

1. Problem in simple words¶

তোমাকে একটা grid (সারি-কলামের ছক) দেওয়া, যেখানে প্রতিটা ঘর হয় '1' (স্থল/land) নয় '0' (জল/water)। পাশাপাশি (উপর-নিচ-বাঁ-ডান, তির্যক না) থাকা land ঘরগুলো মিলে একটা island বানায়। তোমার কাজ: grid-এ মোট কতগুলো আলাদা island আছে গোনো।

grid:
1 1 0 0
1 1 0 0
0 0 1 0
0 0 0 1

island সংখ্যা = 3  (উপরে-বাঁয়ে একটা, মাঝে একটা, নিচে-ডানে একটা)

2. Which basic idea does this inherit from?¶

এই problem দুটো আগের chapter-এর tool জোড়া দেয়:

09 graphs থেকে: grid-টা আসলে একটা লুকানো graph — প্রতিটা land cell একটা node, পাশের land cell-এর সাথে edge। তখন "কতগুলো island" = "কতগুলো connected component"।
06 recursion থেকে: একটা land cell পেলে DFS দিয়ে তার চারপাশের সব যুক্ত land cell-এ ছড়িয়ে গিয়ে পুরো island-টা "ভিজিয়ে" (flood fill) ফেলা।

একা graph-চিন্তা দেয় component-counting framing; একা recursion দেয় ছড়িয়ে পড়ার কৌশল। দুটো মিললে পরিষ্কার flood fill।

3. What is the hidden math or logic?¶

লুকানো logic: connected components গোনা। প্রতিটা নতুন, এখনও-না-ছোঁয়া land cell একটা নতুন component-এর প্রতিনিধি। সেখান থেকে DFS করে পুরো component-কে "visited" চিহ্নিত করলে, পরে সেই cell-গুলো আর নতুন island শুরু করতে পারবে না। তাই কতবার আমরা নতুন DFS শুরু করি = island-এর সংখ্যা।

4. Which data structure is needed?¶

মূল tool: DFS recursion (06)। আলাদাভাবে visited চিহ্ন রাখতে হয় — হয় একটা আলাদা visited set/matrix, নয় (এখানে যেমন) ভিজিয়ে ফেলা cell-কে সরাসরি '0' করে দেওয়া (in-place marking)। implicit graph-টা নিজেই data structure (09)।

5. Why this data structure fits¶

grid-এ adjacency সরাসরি index দিয়ে পাওয়া যায় (r±1, c±1) — আলাদা adjacency list বানাতে হয় না, তাই DFS recursion-ই সবচেয়ে সহজ ও স্বাভাবিক tool। একটা cell ভিজিয়ে '0' করে দিলে সেটা আর গোনায় আসে না, তাই আলাদা visited structure-ও বাঁচে। এই in-place flood fill-ই recursion (06) আর grid-graph (09)-কে এখানে নিখুঁত করে তোলে।

6. Real-life analogy¶

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

7. Visual explanation¶

ছোট grid-এ flood fill, X = এইমাত্র ভেজানো ('0' করা):

শুরু:        (0,0)-তে '1' পেলাম -> DFS শুরু, island গোনা = 1
1 1 0        X 1 0        X X 0        X X 0
1 0 0   ->   1 0 0   ->   X 0 0   ->   X 0 0   (এই island শেষ)
0 0 1        0 0 1        0 0 1        0 0 1

তারপর scan চলতে চলতে (2,2)-তে আরেকটা '1' -> DFS শুরু, island গোনা = 2
শেষ উত্তর = 2

8. Example input and output¶

Input :
1 1 0 0
1 1 0 0
0 0 1 0
0 0 0 1
Output: 3

Edge case 1 (পুরো জল): সব '0'        -> Output: 0
Edge case 2 (পুরো ডাঙা 1x3): 1 1 1   -> Output: 1
Edge case 3 (খালি grid): []          -> Output: 0

9. Brute force thinking¶

আসলে এই problem-এর "brute force"-ও একটা traversal-ই — কিন্তু সরল চিন্তা হলো: প্রতিটা cell ঘুরে দেখি, land পেলে তার চারপাশের সব যুক্ত land-কে আলাদা একটা visited set-এ চিহ্নিত করি, আর নতুন (অচিহ্নিত) land পেলেই counter বাড়াই।

visited = set()
count = 0
for প্রতিটা cell (r, c):
    if grid[r][c] == '1' and (r,c) not in visited:
        count += 1
        dfs(r, c)   # যুক্ত সব land visited-এ ঢোকাও

10. Why brute force is slow¶

এটা আসলে সঠিক ও যথেষ্ট দ্রুত (O(rows·cols)) — flood-fill problem-এ নিখুঁত brute force আর optimal প্রায় একই। "ধীর" version বলতে: যদি প্রতিটা cell থেকে বারবার পুরো grid ঘুরে যুক্ততা যাচাই করতে যেতাম (visited চিহ্ন না রেখে), তখন একই cell বহুবার দেখা হয়ে খরচ ফুলে যেত। visited-marking (বা in-place '0') সেই পুনরাবৃত্তি ঠেকায়।

11. Key observation¶

মূল observation: একটা island একবার পুরো ভিজিয়ে ফেললে, তার কোনো cell আর নতুন island শুরু করতে পারে না। তাই শুধু গুনে রাখলেই হয় — কতবার আমরা একটা টাটকা (এখনও '1') cell-এ DFS শুরু করি। এই এক চিন্তাই counting-টা সহজ করে।

12. Optimized intuition¶

পুরো grid scan করো। যখনই একটা '1' পাও যা এখনও ভেজানো হয়নি: island counter এক বাড়াও, আর সেখান থেকে DFS করে চারদিকের সব যুক্ত '1'-কে '0' করে দাও (ভিজিয়ে দাও)। scan শেষ হলে counter-ই island-সংখ্যা। in-place '0'-করা মানে আলাদা visited লাগে না।

13. Thinking tweak¶

মোচড়: "কোন cell কোন cell-এর সাথে যুক্ত তার পুরো map বানাব" ভাবার বদলে ভাবো "land পেলেই এক ফোঁটা রঙ ফেলে পুরো island মুছে দিই ('0' করি), আর কতবার ফোঁটা ফেলতে হলো গুনি।" component-counting একটা scan + flood fill-এ গলে যায়।

14. Step-by-step dry run¶

Input grid [["1","1"],["0","1"]]:

scan (0,0)='1' → count = 1; DFS: (0,0)→'0', ডানে (0,1)='1'→'0', তার নিচে (1,1)='1'→'0'; চারপাশ আর '1' নেই → island শেষ
scan (0,1) এখন '0' → skip
scan (1,0)='0' → skip
scan (1,1) এখন '0' → skip
শেষ → return count = 1

15. Python solution¶

def num_islands(grid):
    if not grid or not grid[0]:
        return 0
    rows, cols = len(grid), len(grid[0])

    def dfs(r, c):
        # সীমার বাইরে বা জল হলে থামো
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != "1":
            return
        grid[r][c] = "0"              # এই land ভিজিয়ে দাও (visited)
        dfs(r + 1, c)                 # নিচ
        dfs(r - 1, c)                 # উপর
        dfs(r, c + 1)                 # ডান
        dfs(r, c - 1)                 # বাঁ

    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":     # টাটকা land -> নতুন island
                count += 1
                dfs(r, c)             # পুরো island ভিজিয়ে দাও
    return count

# ---- tests ----
g1 = [["1","1","0","0"],
      ["1","1","0","0"],
      ["0","0","1","0"],
      ["0","0","0","1"]]
assert num_islands(g1) == 3

assert num_islands([["0","0"],["0","0"]]) == 0      # পুরো জল
assert num_islands([["1","1","1"]]) == 1            # একটানা ডাঙা
assert num_islands([]) == 0                         # খালি grid
assert num_islands([["1","0","1","0","1"]]) == 3    # বিচ্ছিন্ন ডাঙা
print("সব test pass!")

16. Line-by-line code explanation¶

if not grid or not grid[0]: return 0 — খালি grid edge case।
rows, cols = ... — সীমা ধরে রাখি, যাতে DFS-এ index-চেক করা যায়।
def dfs(r, c) — recursive flood fill (06 recursion)।
if ... or grid[r][c] != "1": return — boundary-র বাইরে গেলে বা জল/already-ভেজানো পেলে থামো — এটাই DFS-এর base case।
grid[r][c] = "0" — এই cell ভিজিয়ে দাও, যাতে আবার গোনা না হয় (in-place visited)।
চারটা dfs(...) — চার প্রতিবেশীতে ছড়াও (grid-graph-এর edge, 09)।
বাইরের double loop — প্রতিটা cell scan; টাটকা '1' পেলে count বাড়িয়ে নতুন DFS।
return count — মোট কতবার নতুন DFS শুরু হলো = island-সংখ্যা।

17. Output walkthrough¶

g1-এ scan করতে করতে প্রথম '1' (0,0)-তে → count 1, DFS উপরে-বাঁয়ের 2x2 ব্লক মুছে দেয়; পরে (2,2)-তে → count 2, একক cell মুছে যায়; শেষে (3,3)-তে → count 3। return 3 — assert pass। পুরো-জল, একটানা-ডাঙা, খালি, বিচ্ছিন্ন case-ও সঠিক। শেষে print: সব test pass!।

18. Time complexity¶

O(rows · cols) — প্রতিটা cell সর্বোচ্চ একবার scan-এ আর একবার DFS-এ ছোঁয়া হয়।

19. Space complexity¶

O(rows · cols) worst case — recursion stack পুরো grid land হলে তত গভীর হতে পারে (06 recursion-এর hidden cost)। in-place marking-এ আলাদা visited লাগে না, তবু stack-টা থাকে।

20. Common mistakes¶

ভেজানো cell চিহ্নিত না করা ('0' না করা বা visited-এ না ঢোকানো) — তখন DFS অসীম লুপে পড়ে বা একই island বহুবার গোনে।
তির্যক (diagonal) প্রতিবেশীও যুক্ত ধরা — এই problem-এ শুধু 4-direction; 8-direction ভুল উত্তর দেয়।
boundary-চেক DFS-এর শুরুতে না রাখা — তখন index out of range crash।
খালি grid ([]) আলাদা না ভাবা — grid[0]-এ crash করতে পারে।

21. Which basic problem this inherits from¶

ভিত্তি: graph-এ connected component / DFS traversal (09 graphs, ../../09-graphs/) + recursion দিয়ে নিজেকে চার দিকে ডাকা (06 recursion, ../../06-recursion-and-backtracking/)। সাধারণ graph DFS-ই এখানে grid-এর উপর implicit-edge দিয়ে চলছে।

22. Similar harder problems¶

Max Area of Island (একই flood fill, কিন্তু area গোনো) — https://leetcode.com/problems/max-area-of-island/
Surrounded Regions (boundary থেকে flood fill) — https://leetcode.com/problems/surrounded-regions/
Number of Islands II (union-find, dynamic যোগ) — https://leetcode.com/problems/number-of-islands-ii/
Pacific Atlantic Water Flow — https://leetcode.com/problems/pacific-atlantic-water-flow/

23. Pattern learned¶

Grid flood fill (connected components via DFS): grid-কে implicit graph ধরে, প্রতিটা টাটকা land থেকে DFS করে পুরো component ভিজিয়ে দাও আর কতবার শুরু করলে গুনো — component-counting-এর canonical রূপ। BFS দিয়েও একই কাজ হয়।

24. Final summary¶

ভবিষ্যতের আমাকে: 2D grid-এ "কতগুলো region / connected blob" শুনলেই flood fill (DFS/BFS) মনে করবে। মূল চাল — cell ভিজিয়ে দাও ('0' বা visited) যাতে দু'বার না গোনো, আর নতুন DFS-শুরুর সংখ্যা গোনো। 4 না 8 direction, সেটা clarify করতে ভুলো না। DFS recursion depth বড় হলে BFS-এ যাওয়ার কথাও বলতে পারো।

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