Jobs

Interviews

Discussions

Painting a Grid With Three Different Colors

Hard

Asked by:

More companies

97 views

Topics:

Dynamic Programming

You are given two integers m and n. Consider an m x n grid where each cell is initially white. You can paint each cell red, green, or blue. All cells must be painted.

Return the number of ways to color the grid with no two adjacent cells having the same color. Since the answer can be very large, return it modulo 10⁹ + 7.

Example 1:

Input: m = 1, n = 1
Output: 3
Explanation: The three possible colorings are shown in the image above.

Example 2:

Input: m = 1, n = 2
Output: 6
Explanation: The six possible colorings are shown in the image above.

Example 3:

Input: m = 5, n = 5
Output: 580986

Constraints:

1 <= m <= 5
1 <= n <= 1000

Try coding it in LeetCode

Painting a Grid With Three Different Colors

Hard

Asked by:

97 views

Topics:

Dynamic Programming

You are given two integers m and n. Consider an m x n grid where each cell is initially white. You can paint each cell red, green, or blue. All cells must be painted.

Return the number of ways to color the grid with no two adjacent cells having the same color. Since the answer can be very large, return it modulo 10⁹ + 7.

Example 1:

Input: m = 1, n = 1
Output: 3
Explanation: The three possible colorings are shown in the image above.

Example 2:

Input: m = 1, n = 2
Output: 6
Explanation: The six possible colorings are shown in the image above.

Example 3:

Input: m = 5, n = 5
Output: 580986

Constraints:

1 <= m <= 5
1 <= n <= 1000

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the grid (number of rows and columns), and what are the maximum possible values for each dimension?
Are there any constraints on which colors can be adjacent to each other (e.g., no two adjacent cells can have the same color)?
How should the grid be represented as input? Is it a 2D array of integers, characters, or some other data structure?
What is the expected output format? Should I return the total number of valid colorings, a single valid coloring, or something else?
Is there a modulo that needs to be applied to the final answer, given the potential for large numbers of valid colorings?

Brute Force Solution

Approach

We need to color a grid where each cell can be one of three colors. The brute force method involves trying every single possible color combination for the entire grid. We will then check if each coloring meets the problem's specific rules.

Here's how the algorithm would work step-by-step:

Start by coloring the first cell with the first color.
Then, color the second cell with the first color and consider the first cell's color.
Keep doing this for all cells, trying out each of the three colors one by one.
Once we color every cell in the grid in one particular way, check to see if this coloring meets the given rules. For example, do adjacent cells have different colors?
If the coloring is valid, we count it or save it.
Repeat this process of trying out color combinations until we have tried every possible coloring of the entire grid.
After testing all the possible ways to color the grid, we return the total count of valid colorings.

Code Implementation

def count_valid_colorings_brute_force(number_of_rows, number_of_columns):
    total_valid_colorings = 0
    grid = [[0] * number_of_columns for _ in range(number_of_rows)]

    def is_valid_coloring(row_index, column_index):
        # Check if the current cell has a different color than its neighbors
        if row_index > 0 and grid[row_index][column_index] == grid[row_index - 1][column_index]:
            return False
        if column_index > 0 and grid[row_index][column_index] == grid[row_index][column_index - 1]:
            return False
        return True

    def solve(row_index, column_index):
        nonlocal total_valid_colorings

        # When we hit past the last cell, count the valid coloring.
        if row_index == number_of_rows:
            total_valid_colorings += 1
            return

        for color in range(1, 4):
            grid[row_index][column_index] = color

            # Check if current coloring is valid, proceed if so.
            if is_valid_coloring(row_index, column_index):
                next_row_index = row_index
                next_column_index = column_index + 1
                if next_column_index == number_of_columns:
                    next_row_index += 1
                    next_column_index = 0
                solve(next_row_index, next_column_index)

    # Start the recursive calls from the first cell.
    solve(0, 0)

    return total_valid_colorings

Big(O) Analysis

Time Complexity

O(3^(m*n)) – The brute force approach explores every possible coloring of the grid, where 'm' is the number of rows and 'n' is the number of columns. Each cell can have 3 different colors. Therefore, there are 3^(m*n) possible colorings. The algorithm iterates through each of these colorings and, for each coloring, validates whether it is a valid configuration based on the problem's constraints. Thus, the time complexity is directly proportional to the number of possible colorings, making it O(3^(m*n)).

Space Complexity

O(N) – The provided plain English explanation describes a recursive brute-force approach to color the grid. In the worst-case scenario, where N is the number of cells in the grid, the algorithm might explore every possible path of color assignments. This leads to a call stack depth proportional to N. Each call stack frame stores the current state of the coloring (i.e., the color assignments made so far). Therefore, the space complexity is dominated by the recursion depth, resulting in O(N) auxiliary space.

Optimal Solution

Approach

We can solve this problem efficiently using a clever approach called dynamic programming. We will break the big grid into smaller problems, solving each row based on the solution of the previous row to avoid redoing work.

Here's how the algorithm would work step-by-step:

Figure out all the valid ways to color a single row, remembering that neighboring cells cannot have the same color.
Now, consider two rows. For each valid coloring of the first row, find all valid colorings of the second row that don't have the same color in the same column.
Imagine building up the grid row by row. For each row, only consider the valid colorings that are possible based on the row above it.
Store the number of ways to color each row ending in each possible valid coloring pattern.
Use the previous row's stored information to quickly calculate the number of ways to color the current row ending in each valid pattern.
Keep doing this until you reach the last row of the grid.
Add up the number of ways to color the last row for all the valid coloring patterns. That sum is your answer.

Code Implementation

def count_ways_to_paint_grid(number_of_rows, number_of_columns):
    number_of_colors = 3
    
    # Generate all possible valid colorings for a single row
    def generate_valid_row_colorings(number_of_columns, number_of_colors):
        if number_of_columns == 0:
            return [[]]
        
        row_colorings = []
        for color in range(number_of_colors):
            for previous_row_coloring in generate_valid_row_colorings(number_of_columns - 1, number_of_colors):
                if not previous_row_coloring or previous_row_coloring[-1] != color:
                    row_colorings.append(previous_row_coloring + [color])
        return row_colorings

    valid_row_colorings = generate_valid_row_colorings(number_of_columns, number_of_colors)
    number_of_valid_row_colorings = len(valid_row_colorings)

    # Initialize DP table to store the number of ways to paint the grid up to each row
    dp_table = [[0] * number_of_valid_row_colorings for _ in range(number_of_rows)]

    # Base case: the first row can be colored in any valid way
    for i in range(number_of_valid_row_colorings):
        dp_table[0][i] = 1

    # Iterate through the rows, building up the DP table
    for row_index in range(1, number_of_rows):
        # Iterate through the valid colorings for the current row
        for current_row_coloring_index in range(number_of_valid_row_colorings):
            # Iterate through the valid colorings for the previous row
            for previous_row_coloring_index in range(number_of_valid_row_colorings):
                # Check if the current row coloring is compatible with the previous row coloring
                is_compatible = True
                for column_index in range(number_of_columns):
                    if valid_row_colorings[current_row_coloring_index][column_index] == \
                       valid_row_colorings[previous_row_coloring_index][column_index]:
                        is_compatible = False
                        break

                # If the colorings are compatible, update the DP table
                if is_compatible:
                    dp_table[row_index][current_row_coloring_index] += \
                        dp_table[row_index - 1][previous_row_coloring_index]

    # Sum up the number of ways to color the last row for all valid colorings
    total_ways_to_paint = 0
    for coloring_index in range(number_of_valid_row_colorings):
        total_ways_to_paint += dp_table[number_of_rows - 1][coloring_index]

    return total_ways_to_paint

# The main function to solve the grid coloring problem
def painting_grid_with_three_colors(number_of_rows, number_of_columns):

    # Handle invalid input cases
    if number_of_rows <= 0 or number_of_columns <= 0:
        return 0

    # Use dynamic programming to count the ways
    result = count_ways_to_paint_grid(number_of_rows, number_of_columns)

    return result

Big(O) Analysis

Time Complexity

O(n) – Let 'n' be the number of rows in the grid. The algorithm iterates through each row to calculate the valid colorings using dynamic programming. For each row, it considers all valid colorings based on the previous row's valid colorings. The number of valid colorings for a single row with 'k' columns is constant (dependent on 'k' but independent of 'n'). Therefore, the algorithm essentially processes each row in constant time since the number of valid colorings is limited. Consequently, the time complexity scales linearly with the number of rows, resulting in O(n).

Space Complexity

O(3^M) – The dominant space complexity stems from storing the number of ways to color each row ending in each possible valid coloring pattern. Since each cell in a row of length M can have 3 colors, the number of valid coloring patterns for a single row is at most 3^M. We store the counts for valid colorings for two rows at a time (the current and the previous row). Thus, the auxiliary space is primarily used to store these counts, leading to a space complexity of O(3^M), where M is the number of columns (width) in the grid. The number of rows, N, does not affect the space complexity.

Edge Cases

Case	How to Handle
Zero rows or columns (n=0 or m=0)	Return 1, as there's only one way to paint an empty grid (do nothing).
One row (n=1)	The number of ways to color each column is 3, and we multiply it m times so return 3^m.
One column (m=1)	The number of ways to color each row is 3, and we multiply it n times so return 3^n.
n and m are both small (e.g., n=1, m=1, n=2, m=2)	The base cases must be handled directly (e.g., n=1, m=1 returns 3).
n and m are both large (e.g., n=100, m=100)	Implement dynamic programming to avoid exponential time complexity, storing intermediate results.
Integer overflow when calculating the total number of ways	Use modulo operator with a large prime number at each step to prevent overflow.
All valid colorings exist	The algorithm should correctly enumerate all possible valid colorings or their count if needed.
Consecutive rows or columns have identical colorings	The DP algorithm should consider the restrictions and avoid such consecutive identical colorings.

Zero rows or columns (n=0 or m=0)

How to Handle:

Return 1, as there's only one way to paint an empty grid (do nothing).

One row (n=1)

How to Handle:

The number of ways to color each column is 3, and we multiply it m times so return 3^m.

One column (m=1)

How to Handle:

The number of ways to color each row is 3, and we multiply it n times so return 3^n.

n and m are both small (e.g., n=1, m=1, n=2, m=2)

How to Handle:

The base cases must be handled directly (e.g., n=1, m=1 returns 3).

n and m are both large (e.g., n=100, m=100)

How to Handle:

Implement dynamic programming to avoid exponential time complexity, storing intermediate results.

Integer overflow when calculating the total number of ways

How to Handle:

Use modulo operator with a large prime number at each step to prevent overflow.

All valid colorings exist

How to Handle:

The algorithm should correctly enumerate all possible valid colorings or their count if needed.

Consecutive rows or columns have identical colorings

How to Handle:

The DP algorithm should consider the restrictions and avoid such consecutive identical colorings.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the grid (number of rows and columns), and what are the maximum possible values for each dimension?
Are there any constraints on which colors can be adjacent to each other (e.g., no two adjacent cells can have the same color)?
How should the grid be represented as input? Is it a 2D array of integers, characters, or some other data structure?
What is the expected output format? Should I return the total number of valid colorings, a single valid coloring, or something else?
Is there a modulo that needs to be applied to the final answer, given the potential for large numbers of valid colorings?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by coloring the first cell with the first color.
Then, color the second cell with the first color and consider the first cell's color.
Keep doing this for all cells, trying out each of the three colors one by one.
Once we color every cell in the grid in one particular way, check to see if this coloring meets the given rules. For example, do adjacent cells have different colors?
If the coloring is valid, we count it or save it.
Repeat this process of trying out color combinations until we have tried every possible coloring of the entire grid.
After testing all the possible ways to color the grid, we return the total count of valid colorings.

Code Implementation

def count_valid_colorings_brute_force(number_of_rows, number_of_columns):
    total_valid_colorings = 0
    grid = [[0] * number_of_columns for _ in range(number_of_rows)]

    def is_valid_coloring(row_index, column_index):
        # Check if the current cell has a different color than its neighbors
        if row_index > 0 and grid[row_index][column_index] == grid[row_index - 1][column_index]:
            return False
        if column_index > 0 and grid[row_index][column_index] == grid[row_index][column_index - 1]:
            return False
        return True

    def solve(row_index, column_index):
        nonlocal total_valid_colorings

        # When we hit past the last cell, count the valid coloring.
        if row_index == number_of_rows:
            total_valid_colorings += 1
            return

        for color in range(1, 4):
            grid[row_index][column_index] = color

            # Check if current coloring is valid, proceed if so.
            if is_valid_coloring(row_index, column_index):
                next_row_index = row_index
                next_column_index = column_index + 1
                if next_column_index == number_of_columns:
                    next_row_index += 1
                    next_column_index = 0
                solve(next_row_index, next_column_index)

    # Start the recursive calls from the first cell.
    solve(0, 0)

    return total_valid_colorings

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Figure out all the valid ways to color a single row, remembering that neighboring cells cannot have the same color.
Now, consider two rows. For each valid coloring of the first row, find all valid colorings of the second row that don't have the same color in the same column.
Imagine building up the grid row by row. For each row, only consider the valid colorings that are possible based on the row above it.
Store the number of ways to color each row ending in each possible valid coloring pattern.
Use the previous row's stored information to quickly calculate the number of ways to color the current row ending in each valid pattern.
Keep doing this until you reach the last row of the grid.
Add up the number of ways to color the last row for all the valid coloring patterns. That sum is your answer.

Code Implementation

def count_ways_to_paint_grid(number_of_rows, number_of_columns):
    number_of_colors = 3
    
    # Generate all possible valid colorings for a single row
    def generate_valid_row_colorings(number_of_columns, number_of_colors):
        if number_of_columns == 0:
            return [[]]
        
        row_colorings = []
        for color in range(number_of_colors):
            for previous_row_coloring in generate_valid_row_colorings(number_of_columns - 1, number_of_colors):
                if not previous_row_coloring or previous_row_coloring[-1] != color:
                    row_colorings.append(previous_row_coloring + [color])
        return row_colorings

    valid_row_colorings = generate_valid_row_colorings(number_of_columns, number_of_colors)
    number_of_valid_row_colorings = len(valid_row_colorings)

    # Initialize DP table to store the number of ways to paint the grid up to each row
    dp_table = [[0] * number_of_valid_row_colorings for _ in range(number_of_rows)]

    # Base case: the first row can be colored in any valid way
    for i in range(number_of_valid_row_colorings):
        dp_table[0][i] = 1

    # Iterate through the rows, building up the DP table
    for row_index in range(1, number_of_rows):
        # Iterate through the valid colorings for the current row
        for current_row_coloring_index in range(number_of_valid_row_colorings):
            # Iterate through the valid colorings for the previous row
            for previous_row_coloring_index in range(number_of_valid_row_colorings):
                # Check if the current row coloring is compatible with the previous row coloring
                is_compatible = True
                for column_index in range(number_of_columns):
                    if valid_row_colorings[current_row_coloring_index][column_index] == \
                       valid_row_colorings[previous_row_coloring_index][column_index]:
                        is_compatible = False
                        break

                # If the colorings are compatible, update the DP table
                if is_compatible:
                    dp_table[row_index][current_row_coloring_index] += \
                        dp_table[row_index - 1][previous_row_coloring_index]

    # Sum up the number of ways to color the last row for all valid colorings
    total_ways_to_paint = 0
    for coloring_index in range(number_of_valid_row_colorings):
        total_ways_to_paint += dp_table[number_of_rows - 1][coloring_index]

    return total_ways_to_paint

# The main function to solve the grid coloring problem
def painting_grid_with_three_colors(number_of_rows, number_of_columns):

    # Handle invalid input cases
    if number_of_rows <= 0 or number_of_columns <= 0:
        return 0

    # Use dynamic programming to count the ways
    result = count_ways_to_paint_grid(number_of_rows, number_of_columns)

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Zero rows or columns (n=0 or m=0)	Return 1, as there's only one way to paint an empty grid (do nothing).
One row (n=1)	The number of ways to color each column is 3, and we multiply it m times so return 3^m.
One column (m=1)	The number of ways to color each row is 3, and we multiply it n times so return 3^n.
n and m are both small (e.g., n=1, m=1, n=2, m=2)	The base cases must be handled directly (e.g., n=1, m=1 returns 3).
n and m are both large (e.g., n=100, m=100)	Implement dynamic programming to avoid exponential time complexity, storing intermediate results.
Integer overflow when calculating the total number of ways	Use modulo operator with a large prime number at each step to prevent overflow.
All valid colorings exist	The algorithm should correctly enumerate all possible valid colorings or their count if needed.
Consecutive rows or columns have identical colorings	The DP algorithm should consider the restrictions and avoid such consecutive identical colorings.

Zero rows or columns (n=0 or m=0)

How to Handle:

Return 1, as there's only one way to paint an empty grid (do nothing).

One row (n=1)

How to Handle:

The number of ways to color each column is 3, and we multiply it m times so return 3^m.

One column (m=1)

How to Handle:

The number of ways to color each row is 3, and we multiply it n times so return 3^n.

n and m are both small (e.g., n=1, m=1, n=2, m=2)

How to Handle:

The base cases must be handled directly (e.g., n=1, m=1 returns 3).

n and m are both large (e.g., n=100, m=100)

How to Handle:

Implement dynamic programming to avoid exponential time complexity, storing intermediate results.

Integer overflow when calculating the total number of ways

How to Handle:

Use modulo operator with a large prime number at each step to prevent overflow.

All valid colorings exist

How to Handle:

The algorithm should correctly enumerate all possible valid colorings or their count if needed.

Consecutive rows or columns have identical colorings

How to Handle:

The DP algorithm should consider the restrictions and avoid such consecutive identical colorings.