Paint Fence

Medium
574.

Paint Fence

Paint Fence is a medium coding problem on dynamic programming, asked in Amazon, Google and Rubrik interviews.

You are painting a fence of n posts using k colours. Every post gets exactly one colour, and no three consecutive posts may share the same colour.

Return the number of ways to paint the fence.

Example 1

Input
n = 3, k = 2
Output
6
Explanation
Only the two all-same paintings are forbidden out of 8.

Example 2

Input
n = 1, k = 1
Output
1

Example 3

Input
n = 7, k = 2
Output
42

Constraints

  • 1 <= n <= 50
  • 1 <= k <= 105
  • The answer fits in a 32-bit integer.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var numWays = function(n, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Paint Fence — Solution in Python, Java & C++

Paint Fence solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon and Google.

Paint Fence is a medium coding problem on dynamic programming, asked in Amazon, Google and Rubrik interviews.

  • Difficulty: Medium
  • Topics: Dynamic Programming
  • Asked at: Amazon, Google, Rubrik
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are painting a fence of n posts using k colours. Every post gets exactly one colour, and no three consecutive posts may share the same colour.

Return the number of ways to paint the fence.

Example 1

Input: n = 3, k = 2
Output: 6
Explanation: Only the two all-same paintings are forbidden out of 8.

Example 2

Input: n = 1, k = 1
Output: 1

Example 3

Input: n = 7, k = 2
Output: 42

Constraints

  • 1 <= n <= 50
  • 1 <= k <= 105
  • The answer fits in a 32-bit integer.

Hints for Paint Fence

  1. Hint 1

    Split the count by whether the last two posts match.

  2. Hint 2

    same[i] needs post i-1 and i equal, which forces post i-2 to differ — so same[i] = diff[i-1].

  3. Hint 3

    diff[i] = (same[i-1] + diff[i-1]) * (k - 1), since any previous state can be followed by a different colour.

How to solve Paint Fence

Track two running counts: paintings whose last two posts match, and paintings whose last two differ. The "no three in a row" rule turns into a one-step recurrence between them.

Approach

  1. Handle n == 1 directly: k ways.
  2. Initialise same = k (both first posts the same colour) and diff = k * (k - 1).
  3. For each further post: the new diff is (same + diff) * (k - 1), and the new same is the old diff.
  4. Return same + diff.

Why it works

A painting ending in two matching posts can only be extended by a different colour, or it would create three in a row. A painting ending in two different posts can be extended by the same colour as the last post (giving a new same) or by any of the other k - 1 colours.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Updating same from the new diff instead of the old one collapses the recurrence.
  • k = 1 works only for n <= 2; the formula already yields 0 beyond that.
  • Intermediate products can exceed 32 bits — accumulate in 64.

Reference solution

Python

def numWays(n: int, k: int) -> int:
    if n == 0:
        return 0
    if n == 1:
        return k
    same = k
    diff = k * (k - 1)
    for _ in range(3, n + 1):
        prev_diff = diff
        diff = (same + diff) * (k - 1)
        same = prev_diff
    return same + diff

Java

public static int numWays(int n, int k) {
    if (n == 0) return 0;
    if (n == 1) return k;
    long same = k;
    long diff = (long) k * (k - 1);
    for (int i = 3; i <= n; i++) {
        long prevDiff = diff;
        diff = (same + diff) * (k - 1);
        same = prevDiff;
    }
    return (int) (same + diff);
}

C++

int numWays(int n, int k) {
    if (n == 0) return 0;
    if (n == 1) return k;
    long long same = k;
    long long diff = (long long) k * (k - 1);
    for (int i = 3; i <= n; i++) {
        long long prevDiff = diff;
        diff = (same + diff) * (k - 1);
        same = prevDiff;
    }
    return (int) (same + diff);
}

JavaScript

var numWays = function(n, k) {
    if (n === 0) return 0;
    if (n === 1) return k;
    let same = k, diff = k * (k - 1);
    for (let i = 3; i <= n; i++) {
        const prevDiff = diff;
        diff = (same + diff) * (k - 1);
        same = prevDiff;
    }
    return same + diff;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 402 dynamic programming problems · the whole catalogue

Learn the technique: Dynamic Programming