Jobs

Interviews

Discussions

Number of Ways to Paint N × 3 Grid

Hard

Asked by:

4 views

Topics:

Dynamic Programming

You have a grid of size n x 3 and you want to paint each cell of the grid with exactly one of the three colors: Red, Yellow, or Green while making sure that no two adjacent cells have the same color (i.e., no two cells that share vertical or horizontal sides have the same color).

Given n the number of rows of the grid, return the number of ways you can paint this grid. As the answer may grow large, the answer must be computed modulo 10⁹ + 7.

Example 1:

Input: n = 1
Output: 12
Explanation: There are 12 possible way to paint the grid as shown.

Example 2:

Input: n = 5000
Output: 30228214

Constraints:

n == grid.length
1 <= n <= 5000

Try coding it in LeetCode

Number of Ways to Paint N × 3 Grid

Hard

Asked by:

4 views

Topics:

Dynamic Programming

Given n the number of rows of the grid, return the number of ways you can paint this grid. As the answer may grow large, the answer must be computed modulo 10⁹ + 7.

Example 1:

Input: n = 1
Output: 12
Explanation: There are 12 possible way to paint the grid as shown.

Example 2:

Input: n = 5000
Output: 30228214

Constraints:

n == grid.length
1 <= n <= 5000

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:

Are there exactly three colors, and does each cell receive exactly one of them?
Are two cells adjacent only when they share a side, so the two ends of a row may use the same color?
Must every pair of cells that share a side have different colors, including cells in neighboring rows?
Is the grid always n rows by three columns?
Should the fast count be returned modulo 1,000,000,007?

Brute Force Solution

Approach

Every row is colored by trying all three colors in each of the three cells. A coloring is rejected when two cells that share a side have the same color, including a cell that matches the cell directly above it. Completed colorings of all n rows are counted, with no stored answers and no modulus.

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

If every row has been colored, add one to the total and return.
Try every combination of three colors for the current row.
Reject the combination when the first cell matches the second or the second matches the third.
After the first row, also reject the combination when any cell matches the cell above it.
Keep the accepted coloring and color the next row.
When the search finishes, return the raw total.

Code Implementation

class Solution:
    def numOfWays(self, grid_height: int) -> int:
        # Represents Red, Green, Blue
        colors = [0, 1, 2]
        total_valid_ways = 0

        def generate_and_count(row_index, previous_row_colors):
            nonlocal total_valid_ways

            # This is the base case: if we have successfully painted all rows, we found one valid way.
            if row_index == grid_height:
                total_valid_ways += 1
                return

            # Explore all possible color combinations for the current row.
            for first_color in colors:
                for second_color in colors:
                    for third_color in colors:
                        # A valid row cannot have adjacent cells with the same color.
                        if first_color == second_color or second_color == third_color:
                            continue

                        current_row_colors = [first_color, second_color, third_color]

                        # For the first row, any valid coloring is acceptable as there's no row above it.
                        if row_index == 0:
                            generate_and_count(row_index + 1, current_row_colors)
                        else:
                            is_coloring_valid_with_previous = True
                            for column_index in range(3):
                                if current_row_colors[column_index] == previous_row_colors[column_index]:
                                    is_coloring_valid_with_previous = False
                                    break
                            
                            # If the current row's coloring is valid with respect to the previous row, proceed.
                            if is_coloring_valid_with_previous:
                                generate_and_count(row_index + 1, current_row_colors)
        
        generate_and_count(0, None)
        return total_valid_ways

Big(O) Analysis

Time Complexity

O(12^n) – Let n be the number of rows. Each row tries twenty-seven color triples, and twelve of them have different side-by-side colors. A later row is also rejected when it matches the row above, but the branching stays on the order of twelve choices per row. The search depth is n, so the number of calls is O(12^n). Checking one triple is constant work, so the total time is O(12^n).

Space Complexity

O(n) – Let n be the number of rows. The search is n calls deep, one call per row. Each call remembers the coloring of the current row, which has the fixed width three. No table of earlier answers is stored. The extra space is O(n).

Optimal Solution

Approach

Valid rows fall into two families: rows whose ends match, and rows whose three colors are all different. There are six rows in each family on the first row. Each later row is counted from the previous two family sizes with a fixed linear combination, and every count is reduced modulo 1,000,000,007.

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

Start both families at six for a grid with one row.
If only one row was requested, return twelve.
For each additional row, compute the next same-ends count as three times the previous same-ends count plus two times the previous different-ends count.
Compute the next different-ends count as two times the previous same-ends count plus two times the previous different-ends count, using the old values for both updates.
Reduce both new counts modulo 1,000,000,007 and replace the old family sizes.
After n rows, return the sum of the two family sizes modulo 1,000,000,007.

Code Implementation

class Solution:
    def numOfWays(self, number_of_rows: int) -> int:
        MOD = 10**9 + 7

        # Initialize counts for the first row (n=1) based on the two pattern types.
        # Type 1 (ABA): 3 choices for A, 2 choices for B. Total = 3 * 2 = 6.
        # Type 2 (ABC): 3 choices for A, 2 for B, 1 for C. Total = 3 * 2 * 1 = 6.
        rows_with_same_ends_count = 6
        rows_with_diff_ends_count = 6

        # Build up the counts for each subsequent row using the totals from the previous row.
        for _ in range(2, number_of_rows + 1):
            # A pattern with the same ends (e.g., ABA) can be formed from:
            # - A previous row with same ends (XYX) in 3 ways (e.g., YXY, YZY, ZYZ).
            # - A previous row with diff ends (XYZ) in 2 ways (e.g., YXY, ZXZ).
            next_rows_with_same_ends = (rows_with_same_ends_count * 3 + rows_with_diff_ends_count * 2) % MOD

            # A pattern with different ends (e.g., ABC) can be formed from:
            # - A previous row with same ends (XYX) in 2 ways (e.g., YZA, ZYA).
            # - A previous row with diff ends (XYZ) in 2 ways (e.g., YZA, ZXY).
            next_rows_with_diff_ends = (rows_with_same_ends_count * 2 + rows_with_diff_ends_count * 2) % MOD

            rows_with_same_ends_count = next_rows_with_same_ends
            rows_with_diff_ends_count = next_rows_with_diff_ends

        total_ways = (rows_with_same_ends_count + rows_with_diff_ends_count) % MOD
        return total_ways

Big(O) Analysis

Time Complexity

O(n) – Let n be the number of rows. A grid of one row returns immediately. Every later row performs a constant amount of arithmetic on the two family sizes and one remainder operation. There are n such rows. The total time is O(n).

Space Complexity

O(1) – Only the two family sizes and the modulus are stored. They are replaced in place as each new row is counted. No coloring of an individual row is retained. The extra space is O(1).

Edge Cases

Case	How to Handle
The grid has a single row	Both versions return twelve, the number of colorings whose side-by-side cells differ.
A row uses the same color on two cells that share a side	That row is rejected.
A row matches the row above in even one column	That coloring is rejected.
The first and third cells of a row use the same color	The row is still allowed when the middle cell uses a different color.
The grid is tall	The fast count is reduced modulo 1,000,000,007, while the exhaustive count is the raw total.

The grid has a single row

How to Handle:

Both versions return twelve, the number of colorings whose side-by-side cells differ.

A row uses the same color on two cells that share a side

How to Handle:

That row is rejected.

A row matches the row above in even one column

How to Handle:

That coloring is rejected.

The first and third cells of a row use the same color

How to Handle:

The row is still allowed when the middle cell uses a different color.

The grid is tall

How to Handle:

The fast count is reduced modulo 1,000,000,007, while the exhaustive count is the raw total.

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:

Are there exactly three colors, and does each cell receive exactly one of them?
Are two cells adjacent only when they share a side, so the two ends of a row may use the same color?
Must every pair of cells that share a side have different colors, including cells in neighboring rows?
Is the grid always n rows by three columns?
Should the fast count be returned modulo 1,000,000,007?

Brute Force Solution

Approach

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

If every row has been colored, add one to the total and return.
Try every combination of three colors for the current row.
Reject the combination when the first cell matches the second or the second matches the third.
After the first row, also reject the combination when any cell matches the cell above it.
Keep the accepted coloring and color the next row.
When the search finishes, return the raw total.

Code Implementation

class Solution:
    def numOfWays(self, grid_height: int) -> int:
        # Represents Red, Green, Blue
        colors = [0, 1, 2]
        total_valid_ways = 0

        def generate_and_count(row_index, previous_row_colors):
            nonlocal total_valid_ways

            # This is the base case: if we have successfully painted all rows, we found one valid way.
            if row_index == grid_height:
                total_valid_ways += 1
                return

            # Explore all possible color combinations for the current row.
            for first_color in colors:
                for second_color in colors:
                    for third_color in colors:
                        # A valid row cannot have adjacent cells with the same color.
                        if first_color == second_color or second_color == third_color:
                            continue

                        current_row_colors = [first_color, second_color, third_color]

                        # For the first row, any valid coloring is acceptable as there's no row above it.
                        if row_index == 0:
                            generate_and_count(row_index + 1, current_row_colors)
                        else:
                            is_coloring_valid_with_previous = True
                            for column_index in range(3):
                                if current_row_colors[column_index] == previous_row_colors[column_index]:
                                    is_coloring_valid_with_previous = False
                                    break
                            
                            # If the current row's coloring is valid with respect to the previous row, proceed.
                            if is_coloring_valid_with_previous:
                                generate_and_count(row_index + 1, current_row_colors)
        
        generate_and_count(0, None)
        return total_valid_ways

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start both families at six for a grid with one row.
If only one row was requested, return twelve.
For each additional row, compute the next same-ends count as three times the previous same-ends count plus two times the previous different-ends count.
Compute the next different-ends count as two times the previous same-ends count plus two times the previous different-ends count, using the old values for both updates.
Reduce both new counts modulo 1,000,000,007 and replace the old family sizes.
After n rows, return the sum of the two family sizes modulo 1,000,000,007.

Code Implementation

class Solution:
    def numOfWays(self, number_of_rows: int) -> int:
        MOD = 10**9 + 7

        # Initialize counts for the first row (n=1) based on the two pattern types.
        # Type 1 (ABA): 3 choices for A, 2 choices for B. Total = 3 * 2 = 6.
        # Type 2 (ABC): 3 choices for A, 2 for B, 1 for C. Total = 3 * 2 * 1 = 6.
        rows_with_same_ends_count = 6
        rows_with_diff_ends_count = 6

        # Build up the counts for each subsequent row using the totals from the previous row.
        for _ in range(2, number_of_rows + 1):
            # A pattern with the same ends (e.g., ABA) can be formed from:
            # - A previous row with same ends (XYX) in 3 ways (e.g., YXY, YZY, ZYZ).
            # - A previous row with diff ends (XYZ) in 2 ways (e.g., YXY, ZXZ).
            next_rows_with_same_ends = (rows_with_same_ends_count * 3 + rows_with_diff_ends_count * 2) % MOD

            # A pattern with different ends (e.g., ABC) can be formed from:
            # - A previous row with same ends (XYX) in 2 ways (e.g., YZA, ZYA).
            # - A previous row with diff ends (XYZ) in 2 ways (e.g., YZA, ZXY).
            next_rows_with_diff_ends = (rows_with_same_ends_count * 2 + rows_with_diff_ends_count * 2) % MOD

            rows_with_same_ends_count = next_rows_with_same_ends
            rows_with_diff_ends_count = next_rows_with_diff_ends

        total_ways = (rows_with_same_ends_count + rows_with_diff_ends_count) % MOD
        return total_ways

Big(O) Analysis

Time Complexity

Space Complexity

O(1) – Only the two family sizes and the modulus are stored. They are replaced in place as each new row is counted. No coloring of an individual row is retained. The extra space is O(1).

Edge Cases

Case	How to Handle
The grid has a single row	Both versions return twelve, the number of colorings whose side-by-side cells differ.
A row uses the same color on two cells that share a side	That row is rejected.
A row matches the row above in even one column	That coloring is rejected.
The first and third cells of a row use the same color	The row is still allowed when the middle cell uses a different color.
The grid is tall	The fast count is reduced modulo 1,000,000,007, while the exhaustive count is the raw total.

The grid has a single row

How to Handle:

Both versions return twelve, the number of colorings whose side-by-side cells differ.

A row uses the same color on two cells that share a side

How to Handle:

That row is rejected.

A row matches the row above in even one column

How to Handle:

That coloring is rejected.

The first and third cells of a row use the same color

How to Handle:

The row is still allowed when the middle cell uses a different color.

The grid is tall

How to Handle:

The fast count is reduced modulo 1,000,000,007, while the exhaustive count is the raw total.