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 <= 501 <= k <= 105The answer fits in a 32-bit integer.
Hints for Paint Fence
Hint 1
Split the count by whether the last two posts match.
Hint 2
same[i]needs posti-1andiequal, which forces posti-2to differ — sosame[i] = diff[i-1].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
- Handle
n == 1directly:kways. - Initialise
same = k(both first posts the same colour) anddiff = k * (k - 1). - For each further post: the new
diffis(same + diff) * (k - 1), and the newsameis the olddiff. - 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
samefrom the newdiffinstead of the old one collapses the recurrence. k = 1works only forn <= 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 + diffJava
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