8.1 BFS / DFS Traversal (Grid & Components)

চিনবেন কীভাবে

"number of islands/components", "flood fill", "shortest steps in a grid/maze", "is there a path", "clone" — BFS = levels/shortest, DFS = explore/components

Demo · approach · কোড — আগে নিজে চেষ্টা, আটকালে খুলুন

Demo: Number of Islands — LC 200 (Medium — Amazon/Google/Meta High)

Statement (Demo): Given an m × n grid of '1' (land) and '0' (water), return the number of islands. An island is land connected horizontally or vertically. Example: grid=[["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]] → 3 | ⚡ m,n ≤ 300

Approach: Scan the grid; on a '1', increase the counter and DFS from there, turning the whole island to '0' ("sinking" it) — so the same island is never counted again.

function numIslands(grid) {
  const m = grid.length,
    n = grid[0].length;
  let count = 0;
  const sink = (i, j) => {
    if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] !== "1") return;
    grid[i][j] = "0"; // visited = sunk
    sink(i + 1, j);
    sink(i - 1, j);
    sink(i, j + 1);
    sink(i, j - 1);
  };
  for (let i = 0; i < m; i++)
    for (let j = 0; j < n; j++)
      if (grid[i][j] === "1") {
        count++;
        sink(i, j);
      }
  return count;
}

Complexity: Time O(m·n), Space O(m·n) worst-case recursion

Demo · Number of Islandsplan · দিন ০৪০ LC 200

নোট · ফাঁকা

My solution — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেWhere I got stuck — কোন trap, ইংরেজিতে

প্রবলেম

Rotting Orangesplan · দিন ০৪৩ LC 994
(multi-source BFS — every rotten orange enters the queue at once)
Statement: In an m × n grid, 0 is empty, 1 a fresh orange, 2 a rotten one. Each minute, fresh oranges next to rotten ones rot. Return the minutes until none is fresh, or -1 if impossible.
Example: grid=[[2,1,1],[1,1,0],[0,1,1]] → 4 | ⚡ m,n ≤ 10
নোট · ফাঁকা
My solution — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেWhere I got stuck — কোন trap, ইংরেজিতে
Clone Graphplan · দিন ০৪৪ LC 133
(a hashmap from old node to new node)
Statement: Given a reference to a node of a connected undirected graph, return a deep copy of the whole graph.
Example: copy every node and edge into brand-new node objects | ⚡ nodes ≤ 100
নোট · ফাঁকা
My solution — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেWhere I got stuck — কোন trap, ইংরেজিতে
Flood Fillplan · দিন ০৩৯ LC 733
Statement: Given an image grid, a start cell (sr, sc) and a color, recolor the start cell and every 4-directionally connected cell of the same original color.
Example: image=[[1,1,1],[1,1,0],[1,0,1]], sr=1, sc=1, color=2 → [[2,2,2],[2,2,0],[2,0,1]] | ⚡ m,n ≤ 50
নোট · ফাঁকা
My solution — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেWhere I got stuck — কোন trap, ইংরেজিতে
Word LadderLC 127
(Hard — implicit graph: word = node, one-letter change = edge; BFS)
Statement: Given beginWord, endWord and a wordList, change one letter at a time (every intermediate word must be in the list). Return the number of words in the shortest sequence, or 0.
Example: beginWord="hit", endWord="cog", wordList=["hot","dot","dog","lot","log","cog"] → 5 | ⚡ wordList.length ≤ 5000
নোট · ফাঁকা
My solution — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেWhere I got stuck — কোন trap, ইংরেজিতে
Word Ladder IILC 126
(Hard — Google High; BFS + parent links, then rebuild the paths)
Statement: Same setup as Word Ladder — return every shortest transformation sequence from beginWord to endWord.
Example: beginWord="hit", endWord="cog", wordList=["hot","dot","dog","lot","log","cog"] → [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]] | ⚡ wordList.length ≤ 500
নোট · ফাঁকা
My solution — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেWhere I got stuck — কোন trap, ইংরেজিতে
Bus RoutesLC 815
(Hard — Uber High; BFS with routes as nodes)
Statement: routes[i] lists every stop of bus i, which loops forever. Given source and target stops, return the fewest buses you must take, or -1.
Example: routes=[[1,2,7],[3,6,7]], source=1, target=6 → 2 | ⚡ routes.length ≤ 500
নোট · ফাঁকা
My solution — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেWhere I got stuck — কোন trap, ইংরেজিতে