Paint Fence - Solution & Explanation
Problem Statement
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:
Input: n = 1, k = 1 Output: 1
Example 3:
Input: n = 7, k = 2 Output: 42
Constraints:
1 <= n <= 501 <= k <= 105- The testcases are generated such that the answer is in the range
[0, 231 - 1]for the givennandk.
Approach Overview
Problem Overview: You are given n fence posts and k paint colors. Each post must be painted one color, but no more than two adjacent posts can share the same color. The task is to compute how many valid painting combinations exist.
Approach 1: Dynamic Programming (O(n) time, O(n) space)
This problem fits naturally into dynamic programming because the number of valid ways for the current post depends on previous posts. Track two states for each position: same[i] (ways where post i has the same color as i-1) and diff[i] (ways where post i has a different color). If the current post uses the same color, the previous pair must have been different to avoid three consecutive matches. That gives same[i] = diff[i-1]. For different colors, you can pick any of the remaining k-1 colors regardless of the previous pair: diff[i] = (same[i-1] + diff[i-1]) * (k - 1). Iterate from post 3 to n while updating these states. The final answer is same[n] + diff[n]. This approach runs in O(n) time and uses O(n) space for the DP arrays.
The key insight is recognizing that the constraint only depends on the last two posts. Instead of tracking full color sequences, you only track whether the last two colors match or differ. This dramatically reduces the state space while keeping transitions simple.
Approach 2: Dynamic Programming (Space Optimization) (O(n) time, O(1) space)
The DP arrays are unnecessary because each state depends only on the previous step. Maintain two variables: same and diff. Initialize for the first two posts: same = k (both posts same color) and diff = k * (k - 1) (two different colors). For every additional post, compute newSame = diff and newDiff = (same + diff) * (k - 1). Update the variables and continue iterating until post n. The final count is same + diff. This keeps the time complexity at O(n) while reducing memory to O(1).
This optimization is common in dynamic programming problems where each state depends only on the previous iteration. The transition logic remains identical; only the storage strategy changes.
Recommended for interviews: Interviewers typically expect the dynamic programming insight that tracks same and diff states. Implementing the O(1) space version shows strong understanding of state transitions and memory optimization. The array-based DP version still demonstrates the correct recurrence and reasoning, but the constant-space variant is the polished solution most candidates present in interviews involving dynamic programming.
Approach 1: Dynamic Programming
We define f[i] to represent the number of ways to paint the fence posts from [0..i] such that the last two posts have different colors, and g[i] to represent the number of ways to paint the fence posts from [0..i] such that the last two posts have the same color. Initially, f[0] = k and g[0] = 0.
When i > 0, we have the following state transition equations:
$
\begin{aligned}
f[i] & = (f[i - 1] + g[i - 1]) times (k - 1) \
g[i] & = f[i - 1]
\end{aligned}
The final answer is f[n - 1] + g[n - 1].
The time complexity is O(n) and the space complexity is O(n), where n$ is the number of fence posts.
Code
Python
Java
C++
Go
TypeScript
Approach 2: Dynamic Programming (Space Optimization)
We notice that f[i] and g[i] are only related to f[i - 1] and g[i - 1]. Therefore, we can use two variables f and g to record the values of f[i - 1] and g[i - 1] respectively, thus optimizing the space complexity to O(1).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming | — |
| Dynamic Programming (Space Optimization) | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (same/diff arrays) | O(n) | O(n) | Good for learning the recurrence and visualizing DP state transitions |
| Dynamic Programming (Space Optimized) | O(n) | O(1) | Preferred solution in interviews or memory-constrained scenarios |
Video Solution
Paint Fence (Leetcode) Dynamic Programming | Explanation with Code • Pepcoding • 57,089 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Paint Fence easy or hard?
Paint Fence Python/Java solution
How to solve Paint Fence in O(n)?
What is the best approach for Paint Fence?
Is Paint Fence asked at Google/Amazon/Meta?
What data structure is used in Paint Fence?
What is the time complexity of Paint Fence?
Ready to solve this problem?
Practice Paint Fence with our built-in code editor and test cases.
Practice on FleetCode