Patterns

DFS on a 2D grid, marking visited cells in place or with set

When to useNumber of islands, flood fill, connected components on grid

recursive

Flood Fill

Find the Number of Islands

number_of_islands

Social Network

twitter_oa_social_network

Word Search

word_search

Pacific Atlantic Water Flowmedium

pacific_atlantic_water_flow · no slots

Longest Increasing Path In Matrix

longest_increasing_path_matrix

BASE CASE

out of bounds OR cell !== target → return

if (i < 0 || i >= image.length || j < 0 || j >= image[0].length) return;
if (image[i][j] !== original) return;

—

if (r < 0 || r >= m || c < 0 || c >= n) return;
if (grid[r][c] !== 1) return;

if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] !== 1) return;

if (visited[node]) return;
visited[node] = true;

if (index === word.length) return true;
if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] !== word[index]) return false;

—

if (memo[i][j] !== 0) return memo[i][j];

[MARK]

mark visited (overwrite cell or add to set)

image[i][j] = replacement;

  visited[node] = true;

grid[r][c] = 0;

grid[i][j] = 0;

visited[node] = true;

const temp = board[r][c];
board[r][c] = '#';

—

memo[i][j] = best;
return best;

RECURSE

dfs in 4 directions

dfs(i + 1, j); dfs(i - 1, j); dfs(i, j + 1); dfs(i, j - 1);

    if (matrix[node][next] === 1 && !visited[next]) dfs(next);

dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1);

dfs(i + 1, j); dfs(i - 1, j); dfs(i, j + 1); dfs(i, j - 1);

for (let next = 0; next < n; next++) {
  if (f[node][next] === 1 && !visited[next]) dfs(next);
}

const found = dfs(r+1, c, index+1) || dfs(r-1, c, index+1) ||
              dfs(r, c+1, index+1) || dfs(r, c-1, index+1);

—

let best = 1;
for (const [di, dj] of [[1,0],[-1,0],[0,1],[0,-1]]) {
  const ni = i + di, nj = j + dj;
  if (ni < 0 || ni >= m || nj < 0 || nj >= n) continue;
  if (matrix[ni][nj] <= matrix[i][j]) continue;
  best = Math.max(best, 1 + dfs(ni, nj));
}

OUTER LOOP

for each cell, if matches: dfs and increment counter

—

for (let i = 0; i < n; i++) {
  if (!visited[i]) { dfs(i); count++; }
}

for (let r = 0; r < m; r++) {
  for (let c = 0; c < n; c++) {
    if (grid[r][c] === 1) { islands++; dfs(r, c); }
  }
}

for (let i = 0; i < m; i++) {
  for (let j = 0; j < n; j++) {
    if (grid[i][j] === 1) { dfs(i, j); count++; }
  }
}

for (let i = 0; i < n; i++) {
  if (!visited[i]) { dfs(i); count++; }
}

for (let r = 0; r < m; r++) {
  for (let c = 0; c < n; c++) {
    if (dfs(r, c, 0)) return true;
  }
}

—

for (let i = 0; i < m; i++) {
  for (let j = 0; j < n; j++) {
    result = Math.max(result, dfs(i, j));
  }
}

RETURN

return counter or aggregated result

return image;

return count;

return islands;

return count;

return count;

return false;

—

return result;