Number of Ways to Paint N × 3 Grid

Number of Ways to Paint N × 3 Grid - Problem

Dynamic Programming Hard

You have a grid of size n × 3 and you want to paint each cell of the grid with exactly one of the three colors: Red, Yellow, or Green.

The constraint is that no two adjacent cells can 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.

Input & Output

Example 1 — Single Row

$ Input: n = 1

› Output: 12

💡 Note: For a 1×3 grid, we have 3 choices for first cell, 2 for second (different from first), and 2 for third (different from second). However, we need to consider both ABA patterns (6 ways) and ABC patterns (6 ways), giving total 12 ways.

Example 2 — Two Rows

$ Input: n = 2

› Output: 54

💡 Note: Starting with 12 ways for first row (6 ABA + 6 ABC), each pattern can transition to valid patterns in the second row based on transition rules.

Example 3 — Three Rows

$ Input: n = 3

› Output: 246

💡 Note: Each additional row multiplies the possibilities based on valid color transitions from the previous row patterns.

Constraints

1 ≤ n ≤ 5000

Visualization

Tap to expand

Asked in

G Google 45 f Facebook 38 a Amazon 32 M Microsoft 28

The key insight is recognizing there are only two types of valid row patterns: ABA (like RGR) and ABC (like RGY). Best approach is Pattern-Based DP tracking transitions between these types. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Memoization (Top-Down DP)	O(n)	O(n)	Cache results of subproblems to avoid recomputation
Pattern-Based Dynamic Programming	O(n)	O(1)	Track valid color patterns and their transitions between rows
Recursive Brute Force	O(3^(3n))	O(3n)	Try all possible color combinations recursively

Memoization (Top-Down DP) — Algorithm Steps

Identify repeating subproblems by row and pattern
Cache results in a memoization table
Return cached result if already computed

Visualization

Tap to expand

Step-by-Step Walkthrough

First Call

Compute and cache result for row pattern

Cache Hit

Return cached result for repeated subproblem

Efficiency

Each state computed only once

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MOD 1000000007
#define MAX_N 5000

static int memo[MAX_N][50];
static int memoSet[MAX_N][50];

int getPatternId(int c1, int c2, int c3) {
    return c1 * 9 + c2 * 3 + c3;
}

void getPattern(int id, int* c1, int* c2, int* c3) {
    *c3 = id % 3;
    *c2 = (id / 3) % 3;
    *c1 = id / 9;
}

int isValidPattern(int c1, int c2, int c3) {
    return c1 != c2 && c2 != c3;
}

int isCompatible(int prevId, int currId) {
    if (prevId == -1) return 1;
    
    int p1, p2, p3, c1, c2, c3;
    getPattern(prevId, &p1, &p2, &p3);
    getPattern(currId, &c1, &c2, &c3);
    
    return p1 != c1 && p2 != c2 && p3 != c3;
}

int countWays(int row, int prevPatternId, int n) {
    if (row == n) return 1;
    
    int memoIdx = prevPatternId + 1;
    if (memoSet[row][memoIdx]) return memo[row][memoIdx];
    
    int ways = 0;
    for (int c1 = 0; c1 < 3; c1++) {
        for (int c2 = 0; c2 < 3; c2++) {
            for (int c3 = 0; c3 < 3; c3++) {
                if (isValidPattern(c1, c2, c3)) {
                    int patternId = getPatternId(c1, c2, c3);
                    if (isCompatible(prevPatternId, patternId)) {
                        ways = (ways + countWays(row + 1, patternId, n)) % MOD;
                    }
                }
            }
        }
    }
    
    memo[row][memoIdx] = ways;
    memoSet[row][memoIdx] = 1;
    return ways;
}

int solution(int n) {
    memset(memoSet, 0, sizeof(memoSet));
    return countWays(0, -1, n);
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", solution(n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each row has at most constant number of states to compute once

✓ Linear Growth

Space Complexity

O(n)

Memoization table stores results for n rows and recursion stack depth n

⚡ Linearithmic Space

28.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Memoization (Top-Down DP) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler