Skip to content

012 — Number of Islands

Source

  • Original source: Classic BFS flood-fill exercise
  • Platform: LeetCode — https://leetcode.com/problems/number-of-islands/
  • Topic: queue (BFS frontier)
  • Difficulty: Medium
  • Pattern: BFS frontier — queue
  • Basic idea inherited from: সাধারণ queue discipline; পূর্ণ graph theory ../../09-graphs/-এ

1. Problem in simple words

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

grid:
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
-> 3 দ্বীপ (উপরের-বাঁয়ের block, মাঝের একক ঘর, নিচের-ডানের জোড়া)

2. Which basic idea does this inherit from?

এটা BFS frontier (queue) pattern-এর সরাসরি প্রয়োগ। মূল idea — একটা শুরুর ঘর থেকে ring-এ ring-এ বাইরের দিকে ছড়িয়ে পুরো connected অংশ "ভরে ফেলা" (flood fill)। এই chapter শুধু queue-টা ঠিকঠাক চালাতে শেখায়; দ্বীপ গোনা, connectivity, traversal-এর পূর্ণ তত্ত্ব থাকে ../../09-graphs/-এ। এখানে grid-ই আমাদের graph, প্রতিটা স্থল-ঘর একটা node, পাশাপাশি স্থল-ঘরের মধ্যে edge।

3. What is the hidden math or logic?

লুকানো logic হলো connected components গোনা। পুরো grid scan করো; যখনই একটা না-দেখা স্থল-ঘর পাও, সেটা একটা নতুন দ্বীপের সূচনা — counter এক বাড়াও — তারপর BFS দিয়ে সেই দ্বীপের সব ঘর খুঁজে visited mark করে দাও, যাতে একই দ্বীপ আবার গোনা না হয়। scan শেষ হলে counter-ই উত্তর।

correctness-এর চাবি: একবার BFS পুরো component-টা নিঃশেষ করে ফেলে, তাই বাইরের loop প্রতিটা component-কে ঠিক একবার করে "নতুন" হিসেবে পায়।

4. Which data structure is needed?

একটা queue (Python-এ collections.deque) BFS frontier ধরে রাখতে। সাথে একটা visited 2D array (বা grid নিজেই mutate করা) যাতে কোনো ঘর দুবার process না হয়। queue-তে আমরা ঘরের (row, col) জোড়া রাখি।

5. Why this data structure fits

flood fill মানে "একটা ঘর থেকে শুরু করে তার সব প্রতিবেশী, তারপর তাদের প্রতিবেশী..." — একটা frontier ক্রমে বাইরের দিকে এগোয়। queue-এর FIFO order ঠিক এই ring-by-ring সম্প্রসারণ দেয়: যাকে আগে আবিষ্কার করেছি, তার প্রতিবেশী আগে explore হয়। deque-এর append আর popleft দুটোই O(1)। (দ্বীপ গোনার জন্য DFS-ও চলত, কিন্তু এই chapter queue-discipline practice করাচ্ছে।)

6. Real-life analogy

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

7. Visual explanation

ছোট grid [["1","1","0"],["0","1","0"],["0","0","1"]]-এ BFS frontier:

grid (r,c):       scan এসে প্রথম '1' (0,0) -> দ্বীপ #1 শুরু, BFS:
1 1 0             queue=[(0,0)]      pop(0,0) -> প্রতিবেশী (0,1),(1,0)? (1,0)='0'
0 1 0             enqueue (0,1)      pop(0,1) -> প্রতিবেশী (1,1)='1' enqueue
0 0 1             pop(1,1) -> প্রতিবেশী সব visited/পানি -> দ্বীপ #1 শেষ
                  visited: (0,0),(0,1),(1,1)

scan এগোয় -> পরের না-দেখা '1' হলো (2,2) -> দ্বীপ #2 শুরু, BFS:
                  queue=[(2,2)] pop -> কোনো স্থল-প্রতিবেশী নেই -> দ্বীপ #2 শেষ

মোট দ্বীপ = 2

8. Example input and output

Input :
[["1","1","1","1","0"],
 ["1","1","0","1","0"],
 ["1","1","0","0","0"],
 ["0","0","0","0","0"]]            -> Output: 1

Input :
[["1","1","0","0","0"],
 ["1","1","0","0","0"],
 ["0","0","1","0","0"],
 ["0","0","0","1","1"]]            -> Output: 3

Edge case 1 (পুরো পানি)  : [["0"]]          -> 0
Edge case 2 (একক স্থল)   : [["1"]]          -> 1
Edge case 3 (খালি grid)  : []               -> 0

9. Brute force thinking

প্রথম সরল চিন্তাটাও আসলে এটাই — grid scan করো, একটা না-দেখা স্থল পেলে কোনো traversal (BFS বা DFS) দিয়ে গোটা component mark করো, count বাড়াও। "brute force" বলতে যা এড়াতে চাই তা হলো connectivity-র আরও খারাপ উপায়: যেমন প্রতিটা স্থল-জোড়ার মধ্যে আলাদা করে পথ আছে কিনা বারবার যাচাই করা।

প্রতিটা স্থল-ঘর থেকে অন্য প্রতিটা স্থল-ঘরে পথ আছে কিনা খুঁজি -> খুবই অপচয়

10. Why brute force is slow

প্রতিটা স্থল-ঘরের জন্য বারবার অন্যদের সাথে connectivity যাচাই করলে কাজটা ঘরের সংখ্যার বর্গে চলে যায়, কারণ একই ঘর বহুবার পুনরায় explore হয়। flood-fill-এ প্রতিটা ঘর ঠিক একবার visited হয়, তাই কাজ grid-এর আকারের সমানুপাতিক — O(rows × cols)।

11. Key observation

মূল observation: একবার কোনো দ্বীপের একটা ঘর পেলে, সেই দ্বীপের বাকি সব ঘর একটানা BFS-এ পাওয়া যায় — আলাদা করে খোঁজার দরকার নেই। তাই বাইরের scan শুধু "নতুন দ্বীপের প্রথম ঘর" ধরার কাজ করে, আর গোনাটা সেখানেই ঘটে।

12. Optimized intuition

grid-এর প্রতিটা ঘর scan করো। স্থল আর না-দেখা হলে: count এক বাড়াও, ঘরটা queue-তে দাও আর visited mark করো; তারপর queue খালি না হওয়া পর্যন্ত popleft করে চার প্রতিবেশী দেখো — যেটা grid-এর ভেতরে, স্থল আর না-দেখা, তাকে visited mark করে enqueue করো। push করার সময়েই visited mark করা জরুরি, যাতে একই ঘর queue-তে দুবার না ঢোকে।

13. Thinking tweak

মোচড়: grid-টাকে আলাদা ঘরের জাল না ভেবে একটা graph ভাবো — প্রতিটা স্থল-ঘর node, পাশাপাশি স্থল-ঘরের মধ্যে edge। তখন "কয়টা দ্বীপ" প্রশ্নটা পরিণত হয় ক্লাসিক "কয়টা connected component" প্রশ্নে, আর উত্তরটা একটা সাধারণ BFS sweep।

14. Step-by-step dry run

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

  1. scan (0,0) — '1', না-দেখা → দ্বীপ #1, count = 1; BFS: enqueue (0,0), mark visited
  2. pop (0,0) — প্রতিবেশী (0,1)='0', (1,0)='0' — কেউ স্থল নয় → দ্বীপ #1 শেষ
  3. scan (0,1) — '0', এড়িয়ে যাও
  4. scan (1,0) — '0', এড়িয়ে যাও
  5. scan (1,1) — '1', না-দেখা → দ্বীপ #2, count = 2; BFS: pop (1,1), স্থল-প্রতিবেশী নেই → শেষ
  6. scan শেষ → return 2

15. Python solution

from collections import deque

def num_islands(grid):
    if not grid or not grid[0]:
        return 0
    rows, cols = len(grid), len(grid[0])
    visited = [[False] * cols for _ in range(rows)]
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1' and not visited[r][c]:
                count += 1                       # নতুন দ্বীপ পেলাম
                queue = deque([(r, c)])
                visited[r][c] = True
                while queue:
                    cr, cc = queue.popleft()     # FIFO frontier
                    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                        nr, nc = cr + dr, cc + dc
                        if (0 <= nr < rows and 0 <= nc < cols
                                and grid[nr][nc] == '1' and not visited[nr][nc]):
                            visited[nr][nc] = True    # push করার সময়েই mark
                            queue.append((nr, nc))
    return count

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

g2 = [["1", "1", "0", "0", "0"],
      ["1", "1", "0", "0", "0"],
      ["0", "0", "1", "0", "0"],
      ["0", "0", "0", "1", "1"]]
assert num_islands(g2) == 3

assert num_islands([["0"]]) == 0      # পুরো পানি
assert num_islands([["1"]]) == 1      # একক স্থল
assert num_islands([]) == 0           # খালি grid
print("সব test pass!")

16. Line-by-line code explanation

  • if not grid or not grid[0]: return 0 — খালি grid-এ দ্বীপ নেই।
  • visited = [[False]*cols ...] — কোন ঘর process হয়ে গেছে তার হিসাব; grid mutate এড়াতে আলাদা array।
  • if grid[r][c] == '1' and not visited[r][c]: — নতুন দ্বীপের প্রথম ঘর; এখানেই count += 1।
  • queue = deque([(r, c)]) / visited[r][c] = True — BFS শুরু; শুরুর ঘর সাথে সাথে visited।
  • cr, cc = queue.popleft() — FIFO; frontier ring-by-ring বাইরে ছড়ায়।
  • ভেতরের if (...) — প্রতিবেশী grid-এর সীমার ভেতরে, স্থল, না-দেখা হলেই গ্রহণ; visited mark append-এর ঠিক আগে যাতে duplicate না হয়।

17. Output walkthrough

num_islands(g2) → scan উপরের-বাঁয়ের 2×2 block পেয়ে দ্বীপ #1 (BFS পুরো block ভরে), মাঝের একক ঘরে দ্বীপ #2, নিচের-ডানের জোড়ায় দ্বীপ #3 → 3। num_islands([["0"]]) → কোনো স্থল নেই, count 0। সব assert pass করে শেষে print: সব test pass!।

18. Time complexity

O(rows × cols) — প্রতিটা ঘর বাইরের scan-এ একবার দেখা হয়, আর BFS-এ বড়জোর একবার enqueue/dequeue হয়।

19. Space complexity

O(rows × cols) — visited array পুরো grid-এর সমান; queue-ও সবচেয়ে খারাপ ক্ষেত্রে (পুরো grid স্থল) এতটা বড় হতে পারে।

20. Common mistakes

  • ঘর dequeue করার সময় visited mark করা — তখন একই ঘর queue-তে একাধিকবার ঢুকে যায়; mark করতে হয় enqueue-এর সময়।
  • সীমানা check বাদ দেওয়া — 0 <= nr < rows and 0 <= nc < cols না থাকলে grid-এর বাইরে index করে crash।
  • তির্যক প্রতিবেশী যোগ করা — এই problem-এ শুধু 4-দিক (উপর-নিচ-ডান-বাঁ) connectivity।

21. Which basic problem this inherits from

ভিত্তি: queue-র FIFO discipline (BFS frontier)। chapter-এর ../patterns.md-এর Pattern 2 (BFS Frontier) এখানে সরাসরি; connected-component, grid-as-graph, traversal-এর পূর্ণ আলোচনা ../../09-graphs/-এ।

22. Similar harder problems

23. Pattern learned

BFS flood fill / connected components: grid বা graph-এ "কয়টা আলাদা region/group" দেখলে scan করো, নতুন না-দেখা node পেলে count বাড়িয়ে BFS দিয়ে পুরো component visited করো — queue-র FIFO frontier।

24. Final summary

ভবিষ্যতের আমাকে: grid = graph; দ্বীপ = connected component। scan করো, নতুন স্থল পেলে count++ আর BFS দিয়ে পুরো দ্বীপ visited করো; mark করো enqueue-এর সময়। "regions", "groups", "connected", "islands" দেখলে BFS frontier ভাববে; গভীর তত্ত্বের জন্য ../../09-graphs/।

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