Is Paint Fence easy or hard?

Paint Fence is typically classified as a medium difficulty problem. The implementation is short, but recognizing the correct dynamic programming states and recurrence relation requires solid DP intuition.

Paint Fence Python/Java solution

Most implementations compute two DP states: same and diff. Languages like Python, Java, C++, Go, and TypeScript follow the same recurrence relation and loop through n posts while updating these two variables to produce the final count.

How to solve Paint Fence in O(n)?

Iterate through the fence posts while maintaining two values: same (last two posts share the same color) and diff (last two posts use different colors). Update them using same = diff and diff = (same + diff) * (k - 1). This processes each post once, producing an O(n) time algorithm with constant space.

What is the best approach for Paint Fence?

The optimal solution uses dynamic programming by tracking two states: ways where the last two posts have the same color and ways where they differ. Each new post updates these states using the recurrence same = diff_previous and diff = (same_previous + diff_previous) * (k - 1). This runs in O(n) time and can be implemented with O(1) space.

Is Paint Fence asked at Google/Amazon/Meta?

Paint Fence appears in interview preparation lists and has been reported in coding interviews at companies that test dynamic programming fundamentals. Variants of the problem are commonly used by companies like Amazon and Google to evaluate DP state design and recurrence reasoning.

What data structure is used in Paint Fence?

The solution primarily relies on dynamic programming states rather than complex data structures. Implementations either use two DP arrays (same and diff) or two variables for the space-optimized approach.

What is the time complexity of Paint Fence?

The standard dynamic programming solution runs in O(n) time because you iterate through the fence posts once and update constant-time state transitions. The space complexity is O(n) with DP arrays or O(1) with the optimized version that keeps only the previous state.

Description Solution Video 17:30

276. Paint Fence

Medium48.3% acceptance4 companiesPremium elsewhere, free here

You are painting a fence of n posts with k different colors. You must paint the posts following these rules:

Every post must be painted exactly one color.
There cannot be three or more consecutive posts with the same color.

Given the two integers n and k, return the number of ways you can paint the fence.

Example 1:

Input: n = 3, k = 2
Output: 6
Explanation: All the possibilities are shown.
Note that painting all the posts red or all the posts green is invalid because there cannot be three posts in a row with the same color.

Example 2: