Painting the Fence problem

Problem Statement

Given a fence with n posts and k colors, find the number of ways to paint the fence such that no more than 2 consecutive posts have the same color.

Example:

• Input: n = 3, k = 2
• Output: 6

Noob-Friendly Explanation

Imagine you have a fence with 3 wooden posts and 2 paint colors (red and blue). You want to paint every post, but you have one rule: no more than 2 posts in a row can be the same color. So "red-red-red" is NOT allowed, but "red-red-blue" is fine. How many valid color combinations are there? The answer turns out to be 6. This problem counts all such valid ways.

Approach 1: Brute Force (Recursion)

Intuition

For each post, try all k colors. Check if painting the current post with a color violates the rule (3 consecutive same colors). Count all valid combinations.

Algorithm

1. For each post, try all k colors
2. If the current and previous two posts all have the same color, skip this
3. Count all valid complete paintings

public class Solution {
    public int paintFence(int n, int k, int[] colors, int pos) {
        if (pos == n) return 1; // successfully painted all posts

        int ways = 0;
        for (int c = 1; c <= k; c++) {
            colors[pos] = c;
            // Check: not 3 consecutive same colors
            if (pos >= 2 && colors[pos] == colors[pos - 1]
                         && colors[pos] == colors[pos - 2]) {
                continue; // skip invalid
            }
            ways += paintFence(n, k, colors, pos + 1);
        }
        return ways;
    }

    public int countWays(int n, int k) {
        return paintFence(n, k, new int[n], 0);
    }
}

Complexity Analysis

• Time Complexity: O(k^n) - Each post has k choices, n posts deep
• Space Complexity: O(n) - Array to store current painting + recursion stack

Approach 2: Optimal (Iterative DP)

Intuition

Track two categories: how many ways end with two same colored posts, and how many end with two different colored posts.

• same: last two posts are the same color. The next post MUST be different → contributes to next diff.
• diff: last two posts are different. The next post can be same or different.

Algorithm

1. For 1 post: total = k
2. For 2 posts: same = k, diff = k*(k-1)
3. For each post from 3 to n:
   • newSame = diff (can only repeat if previous two were different)
   • newDiff = (same + diff) * (k - 1)
4. Answer = same + diff

public class Solution {
    public long countWays(int n, int k) {
        if (n == 1) return k;

        // For 2 posts
        long same = k;           // both posts same color
        long diff = (long) k * (k - 1); // both posts different color

        for (int i = 3; i <= n; i++) {
            long newSame = diff;
            long newDiff = (same + diff) * (k - 1);
            same = newSame;
            diff = newDiff;
        }

        return same + diff;
    }
}

Complexity Analysis

• Time Complexity: O(n) - Single loop from 3 to n
• Space Complexity: O(1) - Only two variables used