Paint Fence

How it works

Since the recurrence only depends on the previous two values, we do not need to store the entire array. We can use two variables to track totalWays(i - 1) and totalWays(i - 2), updating them as we iterate.

This optimization reduces space complexity from O(n) to O(1).

Steps

1. If n is 1, return k.
2. Initialize twoPostsBack = k and onePostBack = k * k.
3. For i from 3 to n:
   • Compute curr = (k - 1) * (onePostBack + twoPostsBack).
   • Shift: twoPostsBack = onePostBack, onePostBack = curr.
4. Return onePostBack.

Complexity

• Time complexity: O(n)
• Space complexity: O(1) constant space

Where n is the number of fence posts.

Things to watch for

Misunderstanding the Three Consecutive Constraint

The problem forbids more than two consecutive posts with the same color. Some solvers mistakenly interpret this as no two adjacent posts can share a color, which is too restrictive. Two adjacent posts can have the same color as long as there is not a third consecutive post with that same color.

Incorrect Base Cases for Small n

When n equals 1, there are exactly k ways. When n equals 2, there are k*k ways since any combination is valid (no three consecutive posts exist yet). Forgetting to handle these base cases or computing them incorrectly leads to wrong answers and potential index-out-of-bounds errors.

Deriving the Wrong Recurrence Relation

The recurrence totalWays(i) = (k-1) * (totalWays(i-1) + totalWays(i-2)) accounts for two scenarios: painting differently from the previous post, or painting the same as the previous post (which requires the two before that to be different). Confusing the logic of when same-color painting is allowed leads to an incorrect formula.

class Solution:
    def numWays(self, n: int, k: int) -> int:
        if n == 1:
            return k

        two_posts_back = k
        one_post_back = k * k

        for i in range(3, n + 1):
            curr = (k - 1) * (one_post_back + two_posts_back)
            two_posts_back = one_post_back
            one_post_back = curr

        return one_post_back

class Solution {
public:
    int numWays(int n, int k) {
        if (n == 1) return k;

        int twoPostsBack = k;
        int onePostBack = k * k;

        for (int i = 3; i <= n; i++) {
            int curr = (k - 1) * (onePostBack + twoPostsBack);
            twoPostsBack = onePostBack;
            onePostBack = curr;
        }

        return onePostBack;
    }
};