What is the time complexity of Flood Fill?

The optimal solution has a time complexity of O(m*n).

What is the space complexity of Flood Fill?

The space complexity is O(m*n).

What data structures are used to solve Flood Fill?

This problem uses Array, Depth-First Search, Breadth-First Search, Matrix. Understanding these concepts is essential for solving this Easy problem efficiently.

What are the key insights for solving Flood Fill?

Insight 1: The core idea is to identify a connected component of pixels with the same color as the starting pixel. Insight 2: Depth-First Search (DFS) or Breadth-First Search (BFS) are suitable algorithms to explore and modify this connected component efficiently.

Which companies ask LeetCode 733. Flood Fill in interviews?

This problem is frequently asked at Akuna Capital, Criteo, OpenAI, Palantir Technologies, Sumo Logic.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Flood Fill - LeetCode 733 Solution

Flood Fill - Complete Solution Guide

Flood Fill is LeetCode problem 733, a Easy level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

You are given an image represented by an m x n grid of integers image , where image[i][j] represents the pixel value of the image. You are also given three integers sr , sc , and color . Your task is to perform a flood fill on the image starting from the pixel image[sr][sc] . To perform a flood fill : Begin with the starting pixel and change its color to color . Perform the same process for each pixel that is directly adjacent (pixels that share a side with the original pixel, either horizontall

Detailed Explanation

The Flood Fill problem asks us to simulate filling a connected region of an image with a new color. We're given an image represented as a 2D array (matrix) of integers, a starting pixel coordinate (sr, sc), and the new color to fill with. The goal is to change the color of the starting pixel and all its directly adjacent (horizontally or vertically) neighbors that have the same original color. This process repeats recursively for the newly colored neighbors until no more adjacent pixels with the original color can be found. The final modified image should be returned.

Solution Approach

The provided solutions utilize Depth-First Search (DFS) to traverse the connected component of pixels with the same color as the starting pixel. The algorithm begins at the given starting pixel (sr, sc) and recursively explores its four adjacent neighbors (up, down, left, right). For each neighbor, it checks if the neighbor is within the bounds of the image, and if its color matches the original color of the starting pixel. If both conditions are met, the neighbor's color is changed to the new color, and the DFS process is recursively called on that neighbor. This continues until all reachable pixels with the original color have been colored with the new color.

Step-by-Step Algorithm

Step 1: Get the original color of the starting pixel image[sr][sc].
Step 2: If the original color is the same as the new color, return the image immediately (no changes needed).
Step 3: Define a recursive DFS function that takes the current row and column indices as input.
Step 4: Inside the DFS function, check the base cases: if the current pixel is out of bounds or if its color is not the original color, return (stop recursion).
Step 5: If the current pixel is within bounds and its color is the original color, change its color to the new color.
Step 6: Recursively call the DFS function on the four adjacent neighbors: (row + 1, col), (row - 1, col), (row, col + 1), and (row, col - 1).
Step 7: After the DFS function completes its execution (i.e., all connected pixels have been filled), return the modified image.

Key Insights

Insight 1: The core idea is to identify a connected component of pixels with the same color as the starting pixel.
Insight 2: Depth-First Search (DFS) or Breadth-First Search (BFS) are suitable algorithms to explore and modify this connected component efficiently.
Insight 3: A crucial optimization is to check if the original color is the same as the new color to avoid unnecessary computations and infinite recursion in some implementations.

Complexity Analysis

Time Complexity: O(m*n)

Space Complexity: O(m*n)

Topics

This problem involves: Array, Depth-First Search, Breadth-First Search, Matrix.

Companies

Asked at: Akuna Capital, Criteo, OpenAI, Palantir Technologies, Sumo Logic.

Flood Fill | LeetCode 733

Easy

Array Depth-First Search Breadth-First Search Matrix

Time: O(m*n)Space: O(m*n)

Solution Code

Available in:

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int originalColor = image[sr][sc];
        if (originalColor == color) return image;
        fill(image, sr, sc, color, originalColor);
        return image;
    }

    private void fill(int[][] image, int sr, int sc, int color, int originalColor) {
        int m = image.length;
        int n = image[0].length;
        if (sr < 0 || sr >= m || sc < 0 || sc >= n || image[sr][sc] != originalColor) return;
        image[sr][sc] = color;
        fill(image, sr + 1, sc, color, originalColor);
        fill(image, sr - 1, sc, color, originalColor);
        fill(image, sr, sc + 1, color, originalColor);
        fill(image, sr, sc - 1, color, originalColor);
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 733: Flood Fill - Detailed explanation and solution approaches.

Topics

Array Depth-First Search Breadth-First Search Matrix

Companies

Akuna CapitalCriteoOpenAIPalantir TechnologiesSumo Logic

Stats

Difficulty:Easy

Languages:4

Companies:5

Problem #:733

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

7 steps

1
Step 1: Get the original color of the starting pixel image[sr][sc].
2
Step 2: If the original color is the same as the new color, return the image immediately (no changes needed).
3
Step 3: Define a recursive DFS function that takes the current row and column indices as input.
4
Step 4: Inside the DFS function, check the base cases: if the current pixel is out of bounds or if its color is not the original color, return (stop recursion).
5
Step 5: If the current pixel is within bounds and its color is the original color, change its color to the new color.
6
Step 6: Recursively call the DFS function on the four adjacent neighbors: (row + 1, col), (row - 1, col), (row, col + 1), and (row, col - 1).
7
Step 7: After the DFS function completes its execution (i.e., all connected pixels have been filled), return the modified image.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(m*n)

💾

Space Complexity

O(m*n)

📝

Why?

The time complexity is determined by the number of pixels visited during the DFS traversal. In the worst case, every pixel is visited. The space complexity arises from the call stack in the recursive DFS implementations or the explicit stack in the iterative solution. The maximum depth of the recursion (or the size of the explicit stack) is proportional to the number of pixels in the image.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Breadth-First Search (BFS)

Instead of using recursion, we can use an iterative BFS approach. We maintain a queue of pixels to process. We start by adding the initial pixel to the queue. Then, while the queue is not empty, we dequeue a pixel, color it, and add its valid (in-bounds and with the original color) neighbors to the queue.

Time: O(m*n)Space: O(m*n) in the worst case (when all pixels have the same color, and the queue contains almost all pixels simultaneously).

Trade-offs: BFS is generally preferred over DFS when the search space is very large to avoid potential stack overflow issues in recursive DFS implementations. However, for this problem, the image size is constrained (<= 50), so both DFS and BFS are acceptable.

✨

Key Insights

1Insight 1: The core idea is to identify a connected component of pixels with the same color as the starting pixel.
2Insight 2: Depth-First Search (DFS) or Breadth-First Search (BFS) are suitable algorithms to explore and modify this connected component efficiently.
3Insight 3: A crucial optimization is to check if the original color is the same as the new color to avoid unnecessary computations and infinite recursion in some implementations.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Edge Cases

Edge case 1: The starting pixel's color is already the same as the new color. The code handles this by checking if `original_color == color` at the beginning and returning the image immediately without making any changes. This prevents infinite recursion.
Edge case 2: The starting pixel is on the boundary of the image. The code handles this by checking `row < 0 or row >= m or col < 0 or col >= n` in the DFS function, ensuring that it doesn't access invalid memory locations.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not checking if the original color is the same as the new color. This can lead to infinite recursion and stack overflow if the base case isn't reached.

✗Common mistake 2: Not checking if the neighboring pixels are within the bounds of the image before accessing them. This will cause an out-of-bounds exception or segmentation fault.

✗Common mistake 3: Forgetting to update the color of the pixel *before* recursively calling the flood fill on its neighbors. If the color isn't updated first, the recursion might continue infinitely or process the same pixel multiple times.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Image editing software uses flood fill algorithms for tools like the paint bucket, allowing users to easily fill regions with a specific color.

🏦Real-world scenario 2: Computer graphics and image processing use flood fill for tasks like object segmentation, where you want to identify and isolate a particular object or region of interest within an image based on color or other properties.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Use this problem to demonstrate clean code practices. Variable naming and code organization matter.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: June 14, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 14

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 7

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jun 30

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

What should I learn from easy problems?

Easy problems introduce core patterns that appear in harder problems. Master basic operations (iteration, conditionals, simple data structures), recognize common patterns (counting, searching, basic transformations), and practice explaining your thought process clearly.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Flood Fill"?

For this easy-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether depth-first search techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?