Flood Fill

🎯

Flood Fill

easyGRAPHFacebookAmazonGoogle

Imagine you are using a paint bucket tool in a drawing app that fills a connected area with a new color. How does the app decide which pixels to change?

💡 Flood Fill is a classic graph traversal problem disguised as a grid coloring task. Beginners often struggle because they don't immediately see the grid as a graph and don't realize that DFS or BFS can be used to explore connected components.

📋

Problem Statement

Given a 2D grid representing an image, a starting pixel (sr, sc), and a new color, replace the color of the starting pixel and all adjacent pixels connected 4-directionally with the same original color with the new color. Return the modified image.

1 ≤ image.length, image[0].length ≤ 500 ≤ sr < image.length0 ≤ sc < image[0].length0 ≤ image[i][j], newColor < 2^16

💡

Example

Input"image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, newColor = 2"

Output[[2,2,2],[2,2,0],[2,0,1]]

Starting at pixel (1,1) with color 1, all connected pixels with color 1 are changed to 2.

• Starting pixel already has the new color → image unchanged
• Image with only one pixel → color changes if different
• Image where no adjacent pixels share the starting pixel's color → only starting pixel changes
• Image with multiple disconnected regions of the same color → only connected region changes

⚠️

Common Mistakes

Not checking if starting pixel's color equals newColor

Infinite recursion or unnecessary processing

✅ Add early exit if original color == newColor

Forgetting boundary checks before accessing neighbors

Index out of bounds runtime error

✅ Always check row and column indices are within valid range

Changing pixel color before checking neighbors

May cause revisiting pixels or incorrect coloring

✅ Change color immediately upon visiting to mark as visited

Using recursion without considering stack overflow

Runtime error on large inputs

✅ Use iterative BFS or DFS with explicit stack for large inputs

Not handling disconnected regions correctly

Incorrect pixels changed

✅ Only change pixels connected 4-directionally with original color

🧠

Brute Force (Pure Recursion DFS)

💡 Starting with a simple recursive DFS helps understand the problem as exploring connected nodes in a graph. It is intuitive but can cause stack overflow on large inputs.

Intuition

From the starting pixel, recursively visit all 4-directionally connected pixels with the same original color and change their color to the new color.

Algorithm

1. Check if the starting pixel's color is already the new color; if yes, return the image as is.
2. Store the original color of the starting pixel.
3. Define a recursive DFS function that changes the color of the current pixel and recursively calls itself on valid neighbors with the original color.
4. Call the DFS function starting from (sr, sc) and return the modified image.

💡 The recursion explores neighbors deeply before backtracking, which can be tricky to visualize but matches the problem's connectedness requirement.

</>

Code

from typing import List

def floodFill(image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
    original_color = image[sr][sc]
    if original_color == newColor:
        return image
    rows, cols = len(image), len(image[0])

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if image[r][c] != original_color:
            return
        image[r][c] = newColor
        dfs(r+1, c)
        dfs(r-1, c)
        dfs(r, c+1)
        dfs(r, c-1)

    dfs(sr, sc)
    return image

# Example usage:
if __name__ == '__main__':
    img = [[1,1,1],[1,1,0],[1,0,1]]
    print(floodFill(img, 1, 1, 2))

Line Notes

original_color = image[sr][sc]Capture the color to replace to avoid changing pixels of other colors

if original_color == newColor:Avoid infinite recursion if the color is already the target color

def dfs(r, c):Define recursive function to explore connected pixels

if r < 0 or r >= rows or c < 0 or c >= cols:Boundary check to prevent index errors

if image[r][c] != original_color:Stop recursion if pixel color differs from original

image[r][c] = newColorChange the pixel color to newColor

dfs(r+1, c)Recurse downwards

dfs(r-1, c)Recurse upwards

dfs(r, c+1)Recurse rightwards

dfs(r, c-1)Recurse leftwards

dfs(sr, sc)Start DFS from the starting pixel

return imageReturn the modified image after flood fill

import java.util.*;

public class FloodFill {
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int originalColor = image[sr][sc];
        if (originalColor == newColor) return image;
        int rows = image.length, cols = image[0].length;
        dfs(image, sr, sc, originalColor, newColor, rows, cols);
        return image;
    }

    private void dfs(int[][] image, int r, int c, int originalColor, int newColor, int rows, int cols) {
        if (r < 0 || r >= rows || c < 0 || c >= cols) return;
        if (image[r][c] != originalColor) return;
        image[r][c] = newColor;
        dfs(image, r + 1, c, originalColor, newColor, rows, cols);
        dfs(image, r - 1, c, originalColor, newColor, rows, cols);
        dfs(image, r, c + 1, originalColor, newColor, rows, cols);
        dfs(image, r, c - 1, originalColor, newColor, rows, cols);
    }

    public static void main(String[] args) {
        FloodFill ff = new FloodFill();
        int[][] img = {{1,1,1},{1,1,0},{1,0,1}};
        int[][] res = ff.floodFill(img, 1, 1, 2);
        System.out.println(Arrays.deepToString(res));
    }
}

Line Notes

int originalColor = image[sr][sc];Store original color to identify pixels to change

if (originalColor == newColor) return image;Prevent unnecessary work and infinite recursion

private void dfs(...)Recursive helper to explore connected pixels

if (r < 0 || r >= rows || c < 0 || c >= cols) return;Boundary check to avoid invalid indices

if (image[r][c] != originalColor) return;Stop recursion if pixel color differs

image[r][c] = newColor;Change pixel color

dfs(image, r + 1, c, ...);Explore downward neighbor

dfs(image, r - 1, c, ...);Explore upward neighbor

dfs(image, r, c + 1, ...);Explore right neighbor

dfs(image, r, c - 1, ...);Explore left neighbor

public static void main(String[] args)Driver code to test the flood fill

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    void dfs(vector<vector<int>>& image, int r, int c, int originalColor, int newColor, int rows, int cols) {
        if (r < 0 || r >= rows || c < 0 || c >= cols) return;
        if (image[r][c] != originalColor) return;
        image[r][c] = newColor;
        dfs(image, r + 1, c, originalColor, newColor, rows, cols);
        dfs(image, r - 1, c, originalColor, newColor, rows, cols);
        dfs(image, r, c + 1, originalColor, newColor, rows, cols);
        dfs(image, r, c - 1, originalColor, newColor, rows, cols);
    }

    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        int originalColor = image[sr][sc];
        if (originalColor == newColor) return image;
        int rows = image.size(), cols = image[0].size();
        dfs(image, sr, sc, originalColor, newColor, rows, cols);
        return image;
    }
};

int main() {
    Solution sol;
    vector<vector<int>> img = {{1,1,1},{1,1,0},{1,0,1}};
    vector<vector<int>> res = sol.floodFill(img, 1, 1, 2);
    for (auto &row : res) {
        for (auto &val : row) cout << val << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

void dfs(vector<vector<int>>& image, int r, int c, int originalColor, int newColor, int rows, int cols)Recursive DFS helper to explore connected pixels

if (r < 0 || r >= rows || c < 0 || c >= cols) return;Boundary check to avoid invalid access

if (image[r][c] != originalColor) return;Stop recursion if pixel color differs

image[r][c] = newColor;Change pixel color to newColor

dfs(image, r + 1, c, ...);Explore downward neighbor

dfs(image, r - 1, c, ...);Explore upward neighbor

dfs(image, r, c + 1, ...);Explore right neighbor

dfs(image, r, c - 1, ...);Explore left neighbor

int originalColor = image[sr][sc];Store original color to identify pixels to change

if (originalColor == newColor) return image;Avoid infinite recursion if colors match

int main()Driver code to test the flood fill implementation

function floodFill(image, sr, sc, newColor) {
    const originalColor = image[sr][sc];
    if (originalColor === newColor) return image;
    const rows = image.length, cols = image[0].length;

    function dfs(r, c) {
        if (r < 0 || r >= rows || c < 0 || c >= cols) return;
        if (image[r][c] !== originalColor) return;
        image[r][c] = newColor;
        dfs(r + 1, c);
        dfs(r - 1, c);
        dfs(r, c + 1);
        dfs(r, c - 1);
    }

    dfs(sr, sc);
    return image;
}

// Example usage:
const img = [[1,1,1],[1,1,0],[1,0,1]];
console.log(floodFill(img, 1, 1, 2));

Line Notes

const originalColor = image[sr][sc];Capture the original color to identify pixels to change

if (originalColor === newColor) return image;Prevent infinite recursion if color is already newColor

function dfs(r, c)Recursive DFS helper to explore connected pixels

if (r < 0 || r >= rows || c < 0 || c >= cols) return;Boundary check to avoid invalid indices

if (image[r][c] !== originalColor) return;Stop recursion if pixel color differs

image[r][c] = newColor;Change pixel color to newColor

dfs(r + 1, c);Explore downward neighbor

dfs(r - 1, c);Explore upward neighbor

dfs(r, c + 1);Explore right neighbor

dfs(r, c - 1);Explore left neighbor

dfs(sr, sc);Start DFS from the starting pixel

return image;Return the modified image after flood fill

⏱

Complexity

TimeO(N) where N is the number of pixels in the image

SpaceO(N) due to recursion stack in worst case when all pixels are connected

Each pixel is visited at most once, but recursion stack can grow to size of connected region

💡 For a 50x50 image, this means at most 2500 pixels visited and recursion depth up to 2500, which may cause stack overflow in some languages.

Interview Verdict: Accepted

This approach works well for small to medium inputs but risks stack overflow on large connected regions.

🧠

Iterative BFS Using Queue

💡 Using BFS with a queue avoids recursion stack overflow and is easier to control. It also naturally explores neighbors level by level.

Intuition

Start from the initial pixel, use a queue to explore all connected pixels with the original color, changing their color to the new color as you go.

Algorithm

1. Check if the starting pixel's color is already the new color; if yes, return the image.
2. Initialize a queue and add the starting pixel.
3. While the queue is not empty, dequeue a pixel, change its color, and enqueue all valid neighbors with the original color.
4. Return the modified image after processing all connected pixels.

💡 The queue ensures pixels are processed in order of discovery, preventing repeated visits and stack overflow.

</>

Code

from collections import deque
from typing import List

def floodFill(image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
    original_color = image[sr][sc]
    if original_color == newColor:
        return image
    rows, cols = len(image), len(image[0])
    queue = deque([(sr, sc)])

    while queue:
        r, c = queue.popleft()
        if image[r][c] == original_color:
            image[r][c] = newColor
            for nr, nc in [(r+1,c), (r-1,c), (r,c+1), (r,c-1)]:
                if 0 <= nr < rows and 0 <= nc < cols and image[nr][nc] == original_color:
                    queue.append((nr, nc))
    return image

# Example usage:
if __name__ == '__main__':
    img = [[1,1,1],[1,1,0],[1,0,1]]
    print(floodFill(img, 1, 1, 2))

Line Notes

from collections import dequeUse deque for efficient FIFO queue operations

if original_color == newColor:Avoid unnecessary processing if colors match

queue = deque([(sr, sc)])Initialize queue with starting pixel

while queue:Process pixels until no more connected pixels remain

r, c = queue.popleft()Dequeue next pixel to process

if image[r][c] == original_color:Check if pixel needs color change

image[r][c] = newColorChange pixel color

for nr, nc in [(r+1,c), (r-1,c), (r,c+1), (r,c-1)]:Check all 4 neighbors

if 0 <= nr < rows and 0 <= nc < cols and image[nr][nc] == original_color:Add valid neighbors with original color to queue

import java.util.*;

public class FloodFill {
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int originalColor = image[sr][sc];
        if (originalColor == newColor) return image;
        int rows = image.length, cols = image[0].length;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{sr, sc});

        while (!queue.isEmpty()) {
            int[] pixel = queue.poll();
            int r = pixel[0], c = pixel[1];
            if (image[r][c] == originalColor) {
                image[r][c] = newColor;
                int[][] directions = {{1,0},{-1,0},{0,1},{0,-1}};
                for (int[] d : directions) {
                    int nr = r + d[0], nc = c + d[1];
                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && image[nr][nc] == originalColor) {
                        queue.offer(new int[]{nr, nc});
                    }
                }
            }
        }
        return image;
    }

    public static void main(String[] args) {
        FloodFill ff = new FloodFill();
        int[][] img = {{1,1,1},{1,1,0},{1,0,1}};
        int[][] res = ff.floodFill(img, 1, 1, 2);
        System.out.println(Arrays.deepToString(res));
    }
}

Line Notes

Queue<int[]> queue = new LinkedList<>();Use queue to implement BFS iteratively

queue.offer(new int[]{sr, sc});Start BFS from the starting pixel

while (!queue.isEmpty()) {Process pixels until queue is empty

int[] pixel = queue.poll();Dequeue pixel to process

if (image[r][c] == originalColor) {Only process pixels with original color

image[r][c] = newColor;Change pixel color

for (int[] d : directions) {Check all 4 neighbors

if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && image[nr][nc] == originalColor)Add valid neighbors to queue

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        int originalColor = image[sr][sc];
        if (originalColor == newColor) return image;
        int rows = image.size(), cols = image[0].size();
        queue<pair<int,int>> q;
        q.push({sr, sc});

        while (!q.empty()) {
            auto [r, c] = q.front(); q.pop();
            if (image[r][c] == originalColor) {
                image[r][c] = newColor;
                vector<pair<int,int>> directions = {{1,0},{-1,0},{0,1},{0,-1}};
                for (auto& d : directions) {
                    int nr = r + d.first, nc = c + d.second;
                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && image[nr][nc] == originalColor) {
                        q.push({nr, nc});
                    }
                }
            }
        }
        return image;
    }
};

int main() {
    Solution sol;
    vector<vector<int>> img = {{1,1,1},{1,1,0},{1,0,1}};
    vector<vector<int>> res = sol.floodFill(img, 1, 1, 2);
    for (auto &row : res) {
        for (auto &val : row) cout << val << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

queue<pair<int,int>> q;Use queue for BFS traversal

q.push({sr, sc});Initialize queue with starting pixel

while (!q.empty()) {Process pixels until queue is empty

auto [r, c] = q.front(); q.pop();Dequeue pixel to process

if (image[r][c] == originalColor) {Process only pixels with original color

image[r][c] = newColor;Change pixel color

for (auto& d : directions) {Check all 4 neighbors

if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && image[nr][nc] == originalColor)Add valid neighbors to queue

function floodFill(image, sr, sc, newColor) {
    const originalColor = image[sr][sc];
    if (originalColor === newColor) return image;
    const rows = image.length, cols = image[0].length;
    const queue = [[sr, sc]];

    while (queue.length > 0) {
        const [r, c] = queue.shift();
        if (image[r][c] === originalColor) {
            image[r][c] = newColor;
            const directions = [[1,0],[-1,0],[0,1],[0,-1]];
            for (const [dr, dc] of directions) {
                const nr = r + dr, nc = c + dc;
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && image[nr][nc] === originalColor) {
                    queue.push([nr, nc]);
                }
            }
        }
    }
    return image;
}

// Example usage:
const img = [[1,1,1],[1,1,0],[1,0,1]];
console.log(floodFill(img, 1, 1, 2));

Line Notes

const queue = [[sr, sc]];Initialize queue with starting pixel

while (queue.length > 0) {Process pixels until queue is empty

const [r, c] = queue.shift();Dequeue pixel to process

if (image[r][c] === originalColor) {Process only pixels with original color

image[r][c] = newColor;Change pixel color

const directions = [[1,0],[-1,0],[0,1],[0,-1]];Define 4-directional neighbors

if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && image[nr][nc] === originalColor)Add valid neighbors to queue

⏱

Complexity

TimeO(N) where N is number of pixels

SpaceO(N) for the queue in worst case

Each pixel is enqueued and processed at most once, queue size can grow to size of connected region

💡 For a 50x50 image, this means at most 2500 pixels processed, but no risk of stack overflow.

Interview Verdict: Accepted

This approach is safer than recursion for large inputs and preferred in production code.

🧠

In-place DFS with Early Exit and Direction Array

💡 This approach optimizes code readability and maintainability by using a direction array and early exit conditions, while still using DFS.

Intuition

Use a direction array to avoid repetitive code and check early if the starting pixel needs no change to reduce unnecessary calls.

Algorithm

1. Check if the starting pixel's color equals newColor; if yes, return image immediately.
2. Store the original color and define a directions array for 4 neighbors.
3. Define a recursive DFS that colors the current pixel and recursively explores neighbors using the directions array.
4. Call DFS from the starting pixel and return the modified image.

💡 Using a directions array reduces code duplication and makes neighbor exploration systematic and less error-prone.

</>

Code

from typing import List

def floodFill(image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
    original_color = image[sr][sc]
    if original_color == newColor:
        return image
    rows, cols = len(image), len(image[0])
    directions = [(1,0), (-1,0), (0,1), (0,-1)]

    def dfs(r, c):
        image[r][c] = newColor
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and image[nr][nc] == original_color:
                dfs(nr, nc)

    dfs(sr, sc)
    return image

# Example usage:
if __name__ == '__main__':
    img = [[1,1,1],[1,1,0],[1,0,1]]
    print(floodFill(img, 1, 1, 2))

Line Notes

directions = [(1,0), (-1,0), (0,1), (0,-1)]Use a directions array to simplify neighbor exploration

if original_color == newColor:Early exit to avoid unnecessary work

def dfs(r, c):Recursive DFS function

image[r][c] = newColorChange pixel color immediately upon visiting

for dr, dc in directions:Iterate over all 4 neighbors systematically

if 0 <= nr < rows and 0 <= nc < cols and image[nr][nc] == original_color:Check bounds and color before recursion

dfs(sr, sc)Start DFS from the starting pixel

return imageReturn the modified image

import java.util.*;

public class FloodFill {
    private static final int[][] directions = {{1,0},{-1,0},{0,1},{0,-1}};

    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int originalColor = image[sr][sc];
        if (originalColor == newColor) return image;
        dfs(image, sr, sc, originalColor, newColor);
        return image;
    }

    private void dfs(int[][] image, int r, int c, int originalColor, int newColor) {
        image[r][c] = newColor;
        int rows = image.length, cols = image[0].length;
        for (int[] d : directions) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && image[nr][nc] == originalColor) {
                dfs(image, nr, nc, originalColor, newColor);
            }
        }
    }

    public static void main(String[] args) {
        FloodFill ff = new FloodFill();
        int[][] img = {{1,1,1},{1,1,0},{1,0,1}};
        int[][] res = ff.floodFill(img, 1, 1, 2);
        System.out.println(Arrays.deepToString(res));
    }
}

Line Notes

private static final int[][] directions = {{1,0},{-1,0},{0,1},{0,-1}};Define directions once for reuse

if (originalColor == newColor) return image;Early exit to avoid unnecessary recursion

image[r][c] = newColor;Change pixel color immediately

for (int[] d : directions) {Iterate over all neighbors systematically

if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && image[nr][nc] == originalColor)Check bounds and color before recursion

dfs(image, nr, nc, originalColor, newColor);Recursive call to neighbor

public static void main(String[] args)Driver code to test the solution

#include <iostream>
#include <vector>
using namespace std;

class Solution {
    const vector<pair<int,int>> directions = {{1,0},{-1,0},{0,1},{0,-1}};
public:
    void dfs(vector<vector<int>>& image, int r, int c, int originalColor, int newColor) {
        image[r][c] = newColor;
        int rows = image.size(), cols = image[0].size();
        for (auto& d : directions) {
            int nr = r + d.first, nc = c + d.second;
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && image[nr][nc] == originalColor) {
                dfs(image, nr, nc, originalColor, newColor);
            }
        }
    }

    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        int originalColor = image[sr][sc];
        if (originalColor == newColor) return image;
        dfs(image, sr, sc, originalColor, newColor);
        return image;
    }
};

int main() {
    Solution sol;
    vector<vector<int>> img = {{1,1,1},{1,1,0},{1,0,1}};
    vector<vector<int>> res = sol.floodFill(img, 1, 1, 2);
    for (auto &row : res) {
        for (auto &val : row) cout << val << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

const vector<pair<int,int>> directions = {{1,0},{-1,0},{0,1},{0,-1}};Store directions for neighbor traversal

if (originalColor == newColor) return image;Early exit to avoid unnecessary recursion

image[r][c] = newColor;Change pixel color immediately

for (auto& d : directions) {Iterate over neighbors systematically

if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && image[nr][nc] == originalColor)Check bounds and color before recursion

dfs(image, nr, nc, originalColor, newColor);Recursive call to neighbor

int main()Driver code to test the solution

function floodFill(image, sr, sc, newColor) {
    const originalColor = image[sr][sc];
    if (originalColor === newColor) return image;
    const rows = image.length, cols = image[0].length;
    const directions = [[1,0],[-1,0],[0,1],[0,-1]];

    function dfs(r, c) {
        image[r][c] = newColor;
        for (const [dr, dc] of directions) {
            const nr = r + dr, nc = c + dc;
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && image[nr][nc] === originalColor) {
                dfs(nr, nc);
            }
        }
    }

    dfs(sr, sc);
    return image;
}

// Example usage:
const img = [[1,1,1],[1,1,0],[1,0,1]];
console.log(floodFill(img, 1, 1, 2));

Line Notes

const directions = [[1,0],[-1,0],[0,1],[0,-1]];Use directions array for neighbor traversal

if (originalColor === newColor) return image;Early exit to avoid unnecessary recursion

image[r][c] = newColor;Change pixel color immediately

for (const [dr, dc] of directions) {Iterate over neighbors systematically

if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && image[nr][nc] === originalColor)Check bounds and color before recursion

dfs(nr, nc);Recursive call to neighbor

dfs(sr, sc);Start DFS from starting pixel

return image;Return modified image

⏱

Complexity

TimeO(N) where N is number of pixels

SpaceO(N) recursion stack in worst case

Each pixel visited once, recursion depth can be large but code is cleaner and less error-prone

💡 This approach balances clarity and performance, suitable for interviews.

Interview Verdict: Accepted

This is a clean and maintainable DFS solution preferred in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In 95% of interviews, coding the clean DFS with direction array or iterative BFS is best for clarity and safety.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force Recursive DFS	O(N)	O(N) recursion stack	Yes (deep recursion)	N/A	Mention only - good to explain intuition
2. Iterative BFS Using Queue	O(N)	O(N) queue	No	N/A	Preferred for large inputs and production code
3. In-place DFS with Direction Array	O(N)	O(N) recursion stack	Yes (deep recursion)	N/A	Best for clean, maintainable code in interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice multiple approaches, and prepare to explain tradeoffs clearly during interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force recursive DFS approach and its intuition.Step 3: Discuss limitations of recursion and introduce iterative BFS.Step 4: Present the clean DFS with direction array for maintainability.Step 5: Code the chosen approach carefully, test with examples and edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of graph traversal, handling of edge cases, recursion vs iteration tradeoffs, and clean code writing.

Common Follow-ups

• What if diagonal neighbors are also connected? → Add diagonal directions to traversal.
• How to handle very large images without stack overflow? → Use iterative BFS or DFS with explicit stack.

💡 These follow-ups test your ability to adapt the solution to variations and scalability concerns.

🔍

Pattern Recognition

When to Use

1) Given a grid or matrix, 2) Need to change or count connected components, 3) Connectivity defined by neighbors (4 or 8 directions), 4) Need to traverse all connected cells starting from a point.

Signature Phrases

'4-directionally connected''starting pixel''change color of connected pixels'

NOT This Pattern When

This is not a shortest path or minimum distance problem, which require different algorithms.

Similar Problems

Number of Islands - counting connected components in a gridSurrounded Regions - capturing surrounded areas using DFS/BFS

Practice

1. What is the time complexity of the optimal Kahn's Algorithm solution for the Course Schedule problem, given V courses and E prerequisite pairs?

medium

A. O(V + E) because each node and edge is processed once in BFS

B. O(V * E) due to nested loops over nodes and edges

C. O(V^2) because each node might be checked against all others

D. O(E) only, since edges dominate the processing time

Solution

1. Step 1: Identify operations on nodes and edges

   Each node is enqueued and dequeued once; each edge is visited once when decrementing in-degree.

2. Step 2: Combine to get total complexity

   Total time is proportional to number of nodes plus number of edges -> O(V + E).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Standard BFS topological sort runs in linear time relative to graph size [OK]

Hint: Each edge and node processed once -> O(V + E) [OK]

Common Mistakes:

• Assuming nested loops cause O(V*E)
• Confusing dense graph worst case with typical complexity
• Ignoring that BFS processes nodes once

2. The following code attempts to find the town judge but contains a subtle bug:

def findJudge(n, trust):
    trust_score = [0] * (n + 1)
    for a, b in trust:
        trust_score[a] -= 1
        trust_score[b] += 1
    for i in range(1, n + 1):
        if trust_score[i] == n - 1:
            return i
    return -1

# Bug: Does not handle n=1 correctly

What is the bug and how to fix it?

medium

A. Line 6: The condition should check if trust_score[i] == n instead of n-1

B. Missing special case for n=1 where the single person is the judge by default

C. Line 3: trust_score array should be size n instead of n+1

D. Line 5: trust_score[a] should be incremented instead of decremented

Solution

1. Step 1: Identify edge case for n=1

   If there is only one person and no trust pairs, that person is trivially the judge.

2. Step 2: Fix by adding a check before main logic

   Return 1 immediately if n == 1 and trust is empty, else proceed.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Without this, code returns -1 incorrectly for single person town [OK]

Hint: Single person town judge must be handled explicitly [OK]

Common Mistakes:

• Ignoring n=1 edge case
• Incorrect trust_score size
• Wrong condition for trust_score check

3. What is the time complexity of the optimal BFS approach for the Surrounded Regions problem on an m x n board?

medium

A. O(m * n) because each cell is visited at most once during BFS marking.

B. O(m * n * (m + n)) because each 'O' region is checked separately.

C. O(m * n * 4) due to checking four neighbors for each cell multiple times.

D. O(m + n) since only boundary cells are initially processed.

Solution

1. Step 1: Analyze BFS traversal

   Each cell is enqueued and dequeued at most once during BFS marking, so total operations are proportional to the number of cells, m*n.

2. Step 2: Consider neighbor checks

   Each cell checks up to 4 neighbors, but this is constant factor, so complexity remains O(m*n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear scan plus BFS over all cells is O(m*n) [OK]

Hint: BFS visits each cell once, so O(m*n) time [OK]

Common Mistakes:

• Confusing BFS with brute force approach leading to O(m*n*(m+n)).
• Counting neighbor checks as multiplicative rather than constant factor.
• Assuming only boundary cells matter for complexity.

4. Suppose the graph edges can have negative weights but no negative cycles. Which algorithm modification or choice correctly computes the shortest network delay times from a start node?

hard

A. Use DFS with path relaxation and memoization to handle negative weights efficiently.

B. Use Dijkstra's algorithm with a priority queue as usual; it handles negative weights correctly.

C. Use BFS since negative weights can be ignored for shortest paths.

D. Use Bellman-Ford algorithm to relax edges repeatedly, detecting negative cycles if any.

Solution

1. Step 1: Recognize that Dijkstra's algorithm fails with negative weights because it assumes non-negative edge costs

   BFS cannot handle weighted edges properly, and DFS with memoization is inefficient and may not terminate correctly.

2. Step 2: Bellman-Ford algorithm is designed to handle negative weights and detect negative cycles by repeated edge relaxation

   It guarantees correct shortest paths if no negative cycles exist.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Bellman-Ford handles negative weights safely [OK]

Hint: Bellman-Ford handles negative weights; Dijkstra does not [OK]

Common Mistakes:

• Using Dijkstra with negative weights incorrectly
• Assuming BFS works for weighted graphs
• Believing DFS with memoization is efficient here

5. Suppose the problem is modified so that water can flow uphill by at most 1 unit of height difference (i.e., from a cell to a neighbor if neighbor's height ≥ current height - 1). Which modification to the BFS approach correctly handles this variant?

hard

A. Change the BFS condition to allow neighbor heights >= current height - 1 and keep the rest unchanged.

B. No change needed; original BFS condition already covers uphill flow.

C. Run BFS from each cell individually to check uphill flow possibility.

D. Use a priority queue BFS (Dijkstra) to handle varying height constraints efficiently.

Solution

1. Step 1: Understand uphill flow constraint

   Allowing uphill flow by 1 unit means edges have weights or costs, not uniform.

2. Step 2: BFS is insufficient

   Standard BFS assumes uniform edge cost; to handle varying constraints, Dijkstra's algorithm with a priority queue is needed.

3. Step 3: Modify algorithm

   Use priority queue BFS (Dijkstra) to explore cells with minimal cost respecting height difference constraints.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Uphill flow requires weighted graph traversal -> Dijkstra [OK]

Hint: Uphill flow needs weighted BFS -> Dijkstra [OK]

Common Mistakes:

• Trying to fix with simple BFS condition change
• Running BFS from every cell causes TLE