004 — Number of Islands¶

Source¶

Original source: Classic grid components exercise
Platform: LeetCode — https://leetcode.com/problems/number-of-islands/
Topic: graphs
Difficulty: Medium
Pattern: connected components on a grid (flood fill + counter)
Basic idea inherited from: flood fill (এই tracker-এর #3, 003-flood-fill.md); grid-as-graph (../bfs.md, ../dfs.md)

1. Problem in simple words¶

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

grid:
  1 1 0 0
  1 0 0 1
  0 0 1 1      <- এখানে 2 টা island

2. Which basic idea does this inherit from?¶

মূল ভিত হলো flood fill (#3)। flood fill এক cell থেকে শুরু করে একই-রঙা প্রতিবেশীতে ছড়িয়ে পুরো region দখল করে। এখানে grid-টাই একটা implicit graph: প্রতিটা জমির cell একটা node, আর পাশাপাশি দুই জমির cell-এর মধ্যে একটা edge। তাই এক island = এক connected component। flood fill দিয়ে একটা গোটা island দখল করো, আর কতবার নতুন করে দখল শুরু করতে হলো — সেটাই island সংখ্যা।

3. What is the hidden math or logic?¶

লুকানো logic: island = connected component, আর component গোনা = কতবার নতুন traversal launch করতে হলো। grid-এর প্রতিটা cell একবার ঘুরে দেখো। এখনো-না-ছোঁয়া কোনো জমির cell পেলে সেটা একটা নতুন island-এর শুরু — counter বাড়াও, তারপর সেই cell থেকে flood fill চালিয়ে গোটা island-টা "ডুবিয়ে দাও" (visited mark করো)। visited mark করার ফলে একই island আর দ্বিতীয়বার গোনা হয় না। মোট launch সংখ্যাই উত্তর।

4. Which data structure is needed?¶

Grid নিজেই — implicit graph; আলাদা adjacency list বানানোর দরকার নেই, neighbor হলো চার দিকের cell।
Visited চিহ্ন — হয় একটা আলাদা visited set/2D array, নয়তো জমির cell-কে জায়গায় '0' করে দেওয়া (in-place sinking)।
Recursion stack (DFS) বা collections.deque (BFS) — একটা island-এর সব cell explore করতে।

5. Why this data structure fits¶

Grid-কে সরাসরি graph ধরা fit করে কারণ neighbor সম্পর্ক fixed আর সহজ — চার দিকের cell, তাই edge গুলো গোনাই যায় না, on the fly হিসাব হয়। Visited চিহ্ন fit করে কারণ cycle এড়াতে আর একই island দুবার না গোনার জন্য প্রতিটা cell ঠিক একবার process হওয়া দরকার। DFS recursion fit করে কারণ flood fill স্বাভাবিকভাবেই recursive; BFS-ও সমান কাজ করে, শুধু deep grid-এ recursion limit-এর ভয় থাকলে নিরাপদ।

6. Real-life analogy¶

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

7. Visual explanation¶

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

শুরু:                ঘোরার সময় (X = sunk/visited):
  1 1 0               X X 0       <- (0,0) থেকে flood, island 1 ডুবে গেল
  1 0 0     ----->    X 0 0
  0 0 1               0 0 1

তারপর scan চলতে চলতে (2,2)-এ নতুন '1':
  X X 0               কোনো প্রতিবেশী জমি নেই, একা একটা cell
  X 0 0     ----->    island 2 ডুবল
  0 0 X

মোট launch = 2  ->  উত্তর 2

8. Example input and output¶

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

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

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

9. Brute force thinking¶

প্রথম সরল চিন্তা: প্রতিটা জমির cell-কে আলাদা ভেবে কোন cell কোন island-এ পড়ে সেটা বারবার মিলিয়ে দেখা — যেমন প্রতিবার নতুন জমি পেলে আগের সব island-এর সাথে adjacency check করা, বা union-find ছাড়াই হাতে হাতে label মেলানো।

1) প্রতিটা জমির cell-কে একটা label দাও
2) দুই জমির cell পাশাপাশি হলে তাদের label এক করার চেষ্টা করো
3) শেষে কতগুলো আলাদা label রইল গোনো

10. Why brute force is slow¶

হাতে হাতে label মেলানো কাজ করলেও জটিল আর ভুলপ্রবণ — কোন label কোনটার সাথে merge হলো তা track করতে গিয়ে effectively একটা দুর্বল disjoint-set লেখা হয়ে যায়, নাহলে বারবার পুরো grid rescan করে quadratic-এর কাছাকাছি চলে যায়। অথচ একটা সরল flood fill প্রতিটা cell ঠিক একবার ছুঁয়ে O(m·n)-তে সব island ডুবিয়ে দেয়। (DSU দিয়ে আরেকটা পরিষ্কার solution হয় — পরে ../../10-disjoint-set-union/-এ ফিরে এসো।)

11. Key observation¶

মূল observation: এখনো-না-ছোঁয়া প্রতিটা জমির cell ঠিক একটা নতুন island-এর জন্ম দেয়। কারণ flood fill সেই cell থেকে পৌঁছানো-যায় এমন সব জমি একবারেই দখল করে নেয়। তাই scan করতে করতে যতবার একটা "তাজা" (visited নয়) জমির cell-এ হোঁচট খেলে, ততবার counter বাড়ানোই যথেষ্ট।

12. Optimized intuition¶

পুরো grid row-by-row scan করো। cell '0' বা ইতিমধ্যে visited হলে এড়িয়ে যাও। cell '1' আর তাজা হলে: counter += 1, তারপর সেই cell থেকে DFS/BFS চালিয়ে গোটা island-টা visited mark করো (in-place হলে '1' → '0')। scan শেষে counter-ই island সংখ্যা। প্রতিটা cell বড়জোর একবার scan-এ আর একবার flood-এ ছোঁয়া হয় — O(m·n)।

13. Thinking tweak¶

মোচড়: "প্রতিটা cell আলাদা করে কোন island-এ তা হিসাব করব" না ভেবে ভাবো "একটা island পেলেই তাকে পুরো ডুবিয়ে দেব, যাতে আর কখনো না দেখি — তাহলে শুধু কতবার নতুন island শুরু হলো সেটা গুনলেই চলে।" merge-এর হিসাব থেকে নেমে এসো একবারের sink-and-count-এ।

14. Step-by-step dry run¶

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

count = 0। scan শুরু row 0।
(0,0) = '1', তাজা → count = 1। flood: (0,0) ডুবল, প্রতিবেশী (0,1)='1' ডুবল, (1,0)='1' ডুবল; ওদের প্রতিবেশী সব '0'/বাইরে। island 1 শেষ।
scan চলতে থাকে: (0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1) — সব হয় '0' নয় ইতিমধ্যে ডুবে গেছে। কিছু হলো না।
(2,2) = '1', তাজা → count = 2। flood: শুধু (2,2), প্রতিবেশী সব পানি/বাইরে। island 2 শেষ।
scan শেষ। return count = 2।

15. Python solution¶

from collections import deque


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

    def sink(r, c):
        # বাইরে গেলে, বা পানি/visited হলে থামো
        if not (0 <= r < R and 0 <= c < C) or grid[r][c] != "1":
            return
        grid[r][c] = "0"                      # ডুবিয়ে দেওয়াই visited-marking
        for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            sink(r + dr, c + dc)

    count = 0
    for r in range(R):
        for c in range(C):
            if grid[r][c] == "1":             # তাজা জমি -> নতুন island
                count += 1
                sink(r, c)                    # গোটা island ডুবিয়ে দাও
    return count


def num_islands_bfs(grid):
    # একই idea, queue দিয়ে (../../04-stack-and-queue/); deep grid-এ recursion-নিরাপদ
    if not grid or not grid[0]:
        return 0
    R, C = len(grid), len(grid[0])
    seen = [[False] * C for _ in range(R)]
    count = 0
    for sr in range(R):
        for sc in range(C):
            if grid[sr][sc] == "1" and not seen[sr][sc]:
                count += 1
                seen[sr][sc] = True           # push করার সময় mark করো
                q = deque([(sr, sc)])
                while q:
                    r, c = q.popleft()
                    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))
    return count


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

assert num_islands_bfs([row[:] for row in g1]) == 2
assert num_islands_bfs([row[:] for row in g2]) == 1
assert num_islands_bfs([row[:] for row in g3]) == 0
# DFS in-place grid বদলায়, তাই প্রতিবার copy পাঠাই
assert num_islands_dfs([row[:] for row in g1]) == 2
assert num_islands_dfs([row[:] for row in g2]) == 1
assert num_islands_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-এ island নেই।
R, C = len(grid), len(grid[0]) — সারি ও কলাম সংখ্যা।
sink(r, c) — bounds বা পানি হলে থামে; নাহলে cell-কে '0' করে চার প্রতিবেশীতে recurse — flood fill।
grid[r][c] = "0" — ডুবানোটাই visited-marking; আলাদা set লাগে না।
বাইরের double loop — প্রতিটা cell scan; তাজা '1' পেলে count += 1 তারপর sink।
BFS version-এ seen[nr][nc] = True ঠিক q.append-এর পাশে — push করার সময় mark, যাতে একই cell queue-তে বারবার না ঢোকে।
test-এ [row[:] for row in g1] — DFS grid-টা in-place বদলায়, তাই প্রতিটা call-কে আলাদা copy দিই।

17. Output walkthrough¶

num_islands_dfs(g1): (0,0) তাজা → count 1, flood ডুবিয়ে দেয় (0,0),(0,1),(1,0)। বাকি scan-এ কিছু তাজা নেই (2,2) পর্যন্ত → count 2। g2 একটাই বড় island → 1। g3 পুরো পানি → 0। BFS version-ও একই ফল দেয়। সব assert pass, শেষে print: সব test pass!।

18. Time complexity¶

O(m · n) — প্রতিটা cell scan-এ একবার, আর flood/BFS-এ বড়জোর একবার করে ছোঁয়া হয়। মোট কাজ cell সংখ্যার সমানুপাতিক।

19. Space complexity¶

O(m · n) worst case — DFS-এ recursion stack এক লম্বা সাপের মতো island-এ পুরো grid গভীরে যেতে পারে; BFS-এ queue ও seen array মিলেও O(m·n)। in-place sink করলে আলাদা visited বাঁচে, কিন্তু stack/queue-র খরচ থাকে।

20. Common mistakes¶

visited mark না করা / cell না ডুবানো — তাহলে flood একই জমিতে ঘুরে infinite recursion বা ভুল গণনা।
diagonal প্রতিবেশী যোগ করে ফেলা — এই problem শুধু চার দিক চায়।
bounds check করার আগে index করা — negative index Python-এ চুপিচুপি wrap করে ভুল cell পড়ে।
DFS solution একই grid-এ বারবার চালিয়ে দ্বিতীয়বার 0 পাওয়া — কারণ প্রথমবারেই সব '1' ডুবে গেছে; copy পাঠাও।

21. Which basic problem this inherits from¶

ভিত্তি: flood fill (#3, 003-flood-fill.md) আর grid-as-graph traversal (../dfs.md, ../bfs.md)। flood fill ছিল এক region রং করা; এই problem সেই flood fill-এর বাইরে একটা counter বসিয়ে "কতগুলো region" বানিয়ে দেয়। এখান থেকেই components-পরিবার শুরু — পরের ধাপ এই island-এর size মাপা (#5)।

22. Similar harder problems¶

Max Area of Island (component-এর size) — https://leetcode.com/problems/max-area-of-island/ (এই tracker-এর #5)
Number of Provinces (adjacency matrix-এ component) — https://leetcode.com/problems/number-of-provinces/ (#6)
Surrounded Regions (border থেকে reverse flood) — https://leetcode.com/problems/surrounded-regions/

23. Pattern learned¶

Components on a grid: "কতগুলো আলাদা region/island/group" = scan করে প্রতিটা তাজা cell থেকে flood fill চালানো আর কতবার নতুন করে শুরু করলে তা গোনা। visited discipline দিয়ে প্রতিটা cell একবার, মোট O(m·n)। DFS সংক্ষিপ্ত, BFS recursion-নিরাপদ।

24. Final summary¶

ভবিষ্যতের আমাকে: "island গোনা = flood fill + counter; তাজা জমি পেলেই গোটা island ডুবিয়ে দাও, কতবার শুরু করলে সেটাই উত্তর।" যখনই grid-এ 'কতগুলো region/island/blob' দেখবে — cell-কে node ভাবো, চার প্রতিবেশীকে edge, আর component গোনার reflex চালাও; পরে একই grid problem-এ DSU দিয়ে দ্বিতীয় solution লিখে তুলনা করো।

25. JavaScript solution (with test cases)¶

const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };

// grid নিজেই implicit graph; sink করাই visited-marking (DFS)
function numIslandsDFS(grid) {
  if (!grid || grid.length === 0 || grid[0].length === 0) return 0;
  const R = grid.length, C = grid[0].length;
  const sink = (r, c) => {
    if (r < 0 || r >= R || c < 0 || c >= C || grid[r][c] !== "1") return;
    grid[r][c] = "0";                                  // ডুবিয়ে দেওয়াই visited-marking
    sink(r - 1, c); sink(r + 1, c); sink(r, c - 1); sink(r, c + 1);
  };
  let count = 0;
  for (let r = 0; r < R; r++) {
    for (let c = 0; c < C; c++) {
      if (grid[r][c] === "1") { count++; sink(r, c); } // তাজা জমি → নতুন island
    }
  }
  return count;
}

// একই idea, queue দিয়ে (deep grid-এ recursion-নিরাপদ)
function numIslandsBFS(grid) {
  if (!grid || grid.length === 0 || grid[0].length === 0) return 0;
  const R = grid.length, C = grid[0].length;
  const seen = Array.from({ length: R }, () => new Array(C).fill(false));
  const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
  let count = 0;
  for (let sr = 0; sr < R; sr++) {
    for (let sc = 0; sc < C; sc++) {
      if (grid[sr][sc] === "1" && !seen[sr][sc]) {
        count++; seen[sr][sc] = true;
        const q = [[sr, sc]]; let head = 0;
        while (head < q.length) {
          const [r, c] = q[head++];
          for (const [dr, dc] of dirs) {
            const nr = r + dr, nc = c + dc;
            if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] === "1" && !seen[nr][nc]) {
              seen[nr][nc] = true; q.push([nr, nc]);
            }
          }
        }
      }
    }
  }
  return count;
}

const clone = (g) => g.map((row) => row.slice());     // DFS in-place বদলায়, তাই copy

// ---- test cases ----
const g1 = [["1", "1", "0"], ["1", "0", "0"], ["0", "0", "1"]];
const g2 = [["1", "1", "1", "1", "0"], ["1", "1", "0", "1", "0"], ["1", "1", "0", "0", "0"], ["0", "0", "0", "0", "0"]];
const g3 = [["0", "0"], ["0", "0"]];
assert(numIslandsBFS(clone(g1)) === 2, "g1 BFS");
assert(numIslandsBFS(clone(g2)) === 1, "g2 BFS");
assert(numIslandsBFS(clone(g3)) === 0, "g3 BFS");
assert(numIslandsDFS(clone(g1)) === 2, "g1 DFS");
assert(numIslandsDFS(clone(g2)) === 1, "g2 DFS");
assert(numIslandsDFS(clone(g3)) === 0, "g3 DFS");
console.log("সব JS test pass!");

JS টীকা: JS-এ 2D grid copy করতে g.map(row => row.slice()) — কারণ DFS version in-place '1'→'0' করে grid বদলে দেয়, তাই প্রতিটা test-এ আলাদা copy দিতে হয় (নাহলে দ্বিতীয়বার 0 আসত)। BFS-এর queue Python-এর deque-র বদলে একটা array + head index দিয়ে চালিয়েছি, shift()-এর O(n) এড়াতে। cell value '1'/'0' string, তাই তুলনায় === "1"।

26. TypeScript solution (with test cases)¶

type Grid = string[][];

function numIslandsDFS(grid: Grid): number {
  if (grid.length === 0 || grid[0].length === 0) return 0;
  const R = grid.length, C = grid[0].length;
  const sink = (r: number, c: number): void => {
    if (r < 0 || r >= R || c < 0 || c >= C || grid[r][c] !== "1") return;
    grid[r][c] = "0";
    sink(r - 1, c); sink(r + 1, c); sink(r, c - 1); sink(r, c + 1);
  };
  let count = 0;
  for (let r = 0; r < R; r++) {
    for (let c = 0; c < C; c++) {
      if (grid[r][c] === "1") { count++; sink(r, c); }
    }
  }
  return count;
}

function numIslandsBFS(grid: Grid): number {
  if (grid.length === 0 || grid[0].length === 0) return 0;
  const R = grid.length, C = grid[0].length;
  const seen: boolean[][] = Array.from({ length: R }, () => new Array(C).fill(false));
  const dirs: [number, number][] = [[-1, 0], [1, 0], [0, -1], [0, 1]];
  let count = 0;
  for (let sr = 0; sr < R; sr++) {
    for (let sc = 0; sc < C; sc++) {
      if (grid[sr][sc] === "1" && !seen[sr][sc]) {
        count++; seen[sr][sc] = true;
        const q: [number, number][] = [[sr, sc]]; let head = 0;
        while (head < q.length) {
          const [r, c] = q[head++];
          for (const [dr, dc] of dirs) {
            const nr = r + dr, nc = c + dc;
            if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] === "1" && !seen[nr][nc]) {
              seen[nr][nc] = true; q.push([nr, nc]);
            }
          }
        }
      }
    }
  }
  return count;
}

const expect = (cond: boolean, msg = ""): void => { if (!cond) throw new Error("FAIL " + msg); };
const clone = (g: Grid): Grid => g.map((row) => row.slice());

const g1: Grid = [["1", "1", "0"], ["1", "0", "0"], ["0", "0", "1"]];
const g2: Grid = [["1", "1", "1", "1", "0"], ["1", "1", "0", "1", "0"], ["1", "1", "0", "0", "0"], ["0", "0", "0", "0", "0"]];
const g3: Grid = [["0", "0"], ["0", "0"]];
expect(numIslandsBFS(clone(g1)) === 2, "2");
expect(numIslandsBFS(clone(g2)) === 1, "1");
expect(numIslandsBFS(clone(g3)) === 0, "0");
expect(numIslandsDFS(clone(g1)) === 2, "2d");
expect(numIslandsDFS(clone(g2)) === 1, "1d");
expect(numIslandsDFS(clone(g3)) === 0, "0d");
console.log("সব TS test pass!");

TS টীকা: type Grid = string[][] একটা alias দিয়ে কোড পড়া সহজ আর signature পরিষ্কার। dirs: [number, number][] — প্রতিটা direction একটা ঠিক দুই-element tuple, তাই for (const [dr, dc] of dirs)-এ dr/dc দুটোই number হিসেবে নিশ্চিত। q: [number, number][] queue-তে শুধু সঠিক [row, col] জোড়া ঢোকা নিশ্চিত করে।

27. কোথায় কাজে লাগে (real-world use)¶

Image segmentation / blob counting: একটা ছবিতে কতগুলো আলাদা object/region/দাগ আছে গোনা — medical imaging, OCR, quality inspection।
Map / satellite analysis: স্যাটেলাইট ছবিতে কতগুলো আলাদা দ্বীপ, জলাশয়, বন বা শহরের অংশ আছে গোনা।
Game board logic: Minesweeper-এর খালি অঞ্চল ছড়ানো, বা একটা গ্রিড-গেমে কতগুলো আলাদা connected group আছে গোনা।
Connected component / clustering: যেকোনো grid বা graph-এ আলাদা গুচ্ছ (cluster) সংখ্যা বের করা — network, circuit, social grouping।
Flood / spill analysis: কোনো এলাকায় কতগুলো আলাদা বন্যা/ছড়ানো অঞ্চল আছে নির্ণয় করা।

মূল সুর: "একটা grid/graph-এ কতগুলো আলাদা connected region আছে" — scan করো, প্রতিটা তাজা cell থেকে flood fill চালাও, কতবার নতুন করে শুরু করলে তা গোনো।

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