Is Painting a Grid With Three Different Colors easy or hard?

Painting a Grid With Three Different Colors is classified as Hard because the naive search space is exponential. The challenge is recognizing that the grid can be processed column by column and compressed into a small set of valid states using dynamic programming.

Painting a Grid With Three Different Colors Python/Java solution

Python and Java implementations typically generate all valid column states using DFS or base-3 enumeration, precompute compatible transitions, then run dynamic programming across columns. Python uses lists and dictionaries for state transitions, while Java often uses arrays for faster DP updates.

How to solve Painting a Grid With Three Different Colors in O(n)?

Pure O(n) time is not achievable because each column must check transitions with multiple valid patterns. The closest efficient approach is O(n * S^2) using pattern-compressed dynamic programming, where S is small due to the constraint m ≤ 5. This keeps the algorithm fast even for n up to 1000.

What is the best approach for Painting a Grid With Three Different Colors?

The most efficient approach uses pattern compression with dynamic programming. Each column is represented as a valid color pattern where vertically adjacent cells differ. Precompute all valid patterns and transitions between compatible columns, then run DP across columns. This reduces the problem from 3^(m*n) possibilities to roughly O(n * S^2) where S is the number of valid column states.

Is Painting a Grid With Three Different Colors asked at Google/Amazon/Meta?

Grid coloring and state-compression dynamic programming problems appear frequently in interviews at companies like Google and Meta. Variants involving column DP, tiling, or bitmask state transitions are common in high-difficulty interview rounds.

What data structure is used in Painting a Grid With Three Different Colors?

The solution mainly uses arrays or hash maps for dynamic programming states and lists to store valid column patterns. Many implementations encode patterns using integers or base-3 representations, similar to techniques used in bitmask dynamic programming.

What is the time complexity of Painting a Grid With Three Different Colors?

The optimized dynamic programming solution runs in O(n * S^2) time, where S is the number of valid column patterns (about 48 when m = 5). Space complexity is O(S) for the iterative DP version or O(n * S) for memoized recursion.

Description Hints 2 Solution Video 50:52

1931. Painting a Grid With Three Different Colors

Hard77.2% acceptance7 companies

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

Asked at 7 companies

Uber Intuit

Google Amazon Microsoft Meta Bloomberg

Topics

Dynamic Programming

Hints open one at a time

Hint 1

Represent each colored column by a bitmask based on each cell color.

Hint 2

Use bitmasks DP with state (currentCell, prevColumn).

50:52

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution