Painting a Grid With Three Different Colors
Understanding the Problem
We have a grid with m rows and n columns. Each cell gets one of 3 colors, and no two cells that share an edge can have the same color. We need to count every valid coloring.
The dimensions are asymmetric: m is at most 5 while n can be up to 1000. That asymmetry drives the solution. If both dimensions were large, the problem would be intractable. With at most 5 rows, we can enumerate every valid way to color a single column, determine which column colorings can sit next to each other, and run a column-by-column DP.
Instead of painting individual cells, we paint one entire column at a time. A "column state" is a tuple of m colors like (R, G, B, R, G). A column state is valid if no two vertically adjacent cells in it share a color. Two column states are compatible if, for every row, the colors in that row differ between the two columns. The answer is the number of sequences of n compatible column states.
Key Constraints:
1 <= m <= 5. The number of ways to assign 3 colors to m cells is 3^m, at most 3^5 = 243. After filtering for vertical adjacency the count of valid column states is even smaller: 3, 6, 12, 24, 48 for m = 1 through 5.1 <= n <= 1000. The approach must scale linearly or at most quadratically in n. With S valid column states (S at most 48), an O(n * S^2) DP is feasible.
Approach 1: Backtracking (Cell by Cell)
Intuition
Paint each cell one at a time in row-major order. For each cell, try all 3 colors and skip a color if it matches the cell above or to the left. When all m*n cells are colored, one valid coloring has been counted.
This is pure backtracking. It is correct, but the branching factor is roughly 2 at each cell (of 3 colors, at least 1 is blocked by the cell above or to the left), giving roughly 2^(m*n) total work. For m=5, n=1000 that is on the order of 2^5000, far beyond what is computable. The value of this version is that it defines exactly what we are counting before we optimize it.
Algorithm
- Traverse cells in row-major order (left to right, top to bottom).
- For each cell, try colors 0, 1, and 2.
- If the color matches the cell directly above (same column, previous row), skip it.
- If the color matches the cell directly to the left (same row, previous column), skip it.
- If we have colored all cells, increment the answer.
- Return the total count modulo 10^9 + 7.
Example Walkthrough
Code
- Time Complexity: O(3^(mn)). At each cell we try up to 3 colors. With mn cells, the worst case is 3^(m*n). In practice pruning reduces this, but it is still exponential.
- Space Complexity: O(m n). We store the grid and the recursion stack depth is m n.
The backtracking explores every complete coloring. The key redundancy: once a column is fully colored, the colorings of all later columns depend only on that column's colors, not on how the earlier columns were filled. The next approach exploits this by tracking entire column states and counting transitions between them.
Approach 2: Column-State DP
Intuition
Since m is at most 5, the number of valid colorings of a single column is small. Each cell can be one of 3 colors, and vertically adjacent cells must differ. Enumerate all valid column colorings, determine which pairs are compatible (no two cells in the same row share a color), and run a DP column by column.
A "column state" is a tuple of m colors. For m = 2, there are 6 valid states: (0,1), (0,2), (1,0), (1,2), (2,0), (2,1). For m = 5, there are 48. These counts are small enough that storing a DP value per state and iterating over compatible pairs is cheap.
The horizontal constraint only relates a column to its immediate neighbor, so the set of colorings allowed for column c+1 depends only on the colors in column c. The grid history before column c does not constrain column c+1. Summing dp[prev] over every state compatible with s therefore counts each valid prefix exactly once, with no double counting and no omissions.
The state space is bounded by 3 * 2^(m-1): the first cell has 3 choices and each cell below has 2 (any color except the one above). For m = 5 that is 48 states, which keeps the DP small regardless of n.
Algorithm
- Generate all valid column states. A column state is a tuple of m values from {0, 1, 2} where no two adjacent values are the same. Use DFS/backtracking to build these.
- For every pair of valid column states, check if they are compatible: for each row, the colors must differ between the two columns.
- Build a compatibility adjacency list: for each state s, store the list of states that can follow s.
- Initialize DP: for the first column, each valid state has count 1.
- For each subsequent column (2 through n), for each valid state s, sum up
dp[prev]for all statesprevcompatible with s. This becomes the newdp[s]. - The answer is the sum of all
dp[s]after processing n columns, taken modulo 10^9 + 7.
Example Walkthrough
Code
- Time Complexity: O(n S^2 + S^2 m). Generating S valid states takes O(S m). Building the compatibility list takes O(S^2 m). The DP runs in O(n * S^2). For m = 5, S = 48, so the DP does about 2.3 million operations for n = 1000.
- Space Complexity: O(S^2 + S). The compatibility list stores at most S^2 entries. The DP arrays use O(S) space. With S = 48, this is negligible.
Each DP step applies the same linear transformation: the new state vector is the transition matrix times the old one. Because every step is identical, the n-1 applications can be collapsed into a single matrix power computed with O(log n) multiplications.
Approach 3: Matrix Exponentiation
Intuition
The column-state DP from Approach 2 is a linear recurrence. At each column, the new DP vector equals the transition matrix T times the old DP vector. After n-1 transitions, the result is T^(n-1) times the initial vector.
Matrix exponentiation computes T^(n-1) in O(S^3 log n) time using repeated squaring. With S at most 48, S^3 is about 110,000, and multiplied by log2(1000) which is about 10, the total is roughly 1.1 million operations. For these constraints that is comparable to Approach 2, but the matrix approach is the one that survives if n grows to, say, 10^18, where the O(n S^2) DP would not.
The same technique applies to any problem that counts paths of length n in a fixed graph.
Algorithm
- Generate all S valid column states and build the S x S transition matrix T where T[i][j] = 1 if state j can follow state i (compatible), and 0 otherwise.
- Start with an initial vector v of size S where every entry is 1 (each valid state is equally reachable in column 1).
- Compute T^(n-1) using matrix exponentiation (repeated squaring). All arithmetic is modulo 10^9 + 7.
- Multiply T^(n-1) by v to get the final DP vector.
- The answer is the sum of all entries in the resulting vector, modulo 10^9 + 7.
Example Walkthrough
Code
- Time Complexity: O(S^3 log n + S^2 m). Building the transition matrix takes O(S^2 m). Matrix exponentiation takes O(S^3 log n) since each matrix multiplication is O(S^3) and we do O(log n) of them. For m = 5, S = 48 and S^3 = 110,592. With log2(1000) roughly 10, the total is about 1.1 million operations.
- Space Complexity: O(S^2). We store the transition matrix and a few intermediate matrices, each of size S x S. For m = 5, that is 48 x 48 = 2304 entries.