Problem link ও উৎস
- **Original source:** Classic grid components exercise
- **Platform:** LeetCode —
- **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](003-flood-fill.md)); grid-as-graph ([../bfs.md](../bfs.md), [../dfs.md](../dfs.md))
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা `m x n` grid দেওয়া আছে, যেখানে প্রতিটা cell হয় `'1'` (জমি) নয়তো `'0'` (পানি)। একটা **island** হলো পাশাপাশি (উপর-নিচ-বাম-ডান) জুড়ে থাকা একগুচ্ছ জমির cell। কতগুলো আলাদা island আছে, সেটা গোনো। কোনাকুনি (diagonal) connection ধরা হয় না — শুধু চার দিকের প্রতিবেশী।
```text
grid:
1 1 0 0
1 0 0 1
0 0 1 1 <- এখানে 2 টা island
```
### Input ও output {#8-example-input-and-output}
```text
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
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
স্যাটেলাইট থেকে তোলা সমুদ্রের একটা ছবি ভাবো — কোথাও কোথাও দ্বীপ। তুমি দ্বীপ গুনতে চাও। একটা দ্বীপের কোনো এক টুকরো জমি দেখলে সেখান থেকে হেঁটে হেঁটে পুরো দ্বীপটা ঘুরে আসো আর প্রতিটা ঘোরা জায়গা পেন্সিল দিয়ে দাগিয়ে রাখো — যাতে আবার গুনে না ফেলো। তারপর ছবির বাকি অংশে নতুন কোনো অদাগানো জমি খোঁজো; পেলে আরেকটা দ্বীপ, আবার পুরোটা দাগাও। যতবার নতুন করে দাগানো শুরু করলে, ততগুলো দ্বীপ।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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-এর ভয় থাকলে নিরাপদ।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা জমির cell-কে আলাদা ভেবে কোন cell কোন island-এ পড়ে সেটা বারবার মিলিয়ে দেখা — যেমন প্রতিবার নতুন জমি পেলে আগের সব island-এর সাথে adjacency check করা, বা union-find ছাড়াই হাতে হাতে label মেলানো।
```text
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/](../../10-disjoint-set-union/README.md)-এ ফিরে এসো।)
### যে বিষয়টি খেয়াল করতে হবে {#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-এ।
### ছবিতে বোঝা {#7-visual-explanation}
`grid = [["1","1","0"],["1","0","0"],["0","0","1"]]` দিয়ে দেখি:
```text
শুরু: ঘোরার সময় (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
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`grid = [["1","1","0"],["1","0","0"],["0","0","1"]]`:
1. `count = 0`। scan শুরু row 0।
2. `(0,0) = '1'`, তাজা → `count = 1`। flood: `(0,0)` ডুবল, প্রতিবেশী `(0,1)='1'` ডুবল, `(1,0)='1'` ডুবল; ওদের প্রতিবেশী সব `'0'`/বাইরে। island 1 শেষ।
3. scan চলতে থাকে: `(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1)` — সব হয় `'0'` নয় ইতিমধ্যে ডুবে গেছে। কিছু হলো না।
4. `(2,2) = '1'`, তাজা → `count = 2`। flood: শুধু `(2,2)`, প্রতিবেশী সব পানি/বাইরে। island 2 শেষ।
5. scan শেষ। return `count = 2`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
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 দিই।
### Output মিলিয়ে দেখা {#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!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
```javascript
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"`।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
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]` জোড়া ঢোকা নিশ্চিত করে।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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 পাঠাও।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: flood fill (#3, [003-flood-fill.md](003-flood-fill.md)) আর grid-as-graph traversal ([../dfs.md](../dfs.md), [../bfs.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) —