Problem Description

You need to paint a fence that has n posts using k different colors. Each post must be painted with exactly one color, and you cannot have three or more consecutive posts painted with the same color.

For example, if you have 3 posts and 2 colors (say red and blue), some valid ways to paint would be:

• red, blue, red
• red, blue, blue
• blue, red, red
• blue, red, blue

But painting all three posts the same color (red, red, red or blue, blue, blue) would be invalid since that creates three consecutive posts with the same color.

The problem asks you to find the total number of different ways you can paint all n posts while following these rules.

The solution uses dynamic programming with two arrays:

• f[i] tracks the number of ways to paint posts 0 to i where the last two posts have different colors
• g[i] tracks the number of ways to paint posts 0 to i where the last two posts have the same color

The key insight is that:

• If the last two posts have different colors (f[i]), the current post can be any of the k-1 colors different from the previous post
• If the last two posts have the same color (g[i]), the current post must be different from the previous two, so we transition from the f[i-1] state

The final answer combines both possibilities: f[n-1] + g[n-1].

Intuition

When thinking about this problem, we need to keep track of whether we can paint the current post with the same color as the previous one or not. This depends on the pattern of the last two posts.

The key observation is that at any post i, we only care about two scenarios:

1. The previous two posts have different colors - in this case, we can paint the current post either the same as the last post or different from it
2. The previous two posts have the same color - in this case, we must paint the current post with a different color to avoid three consecutive posts with the same color

This naturally leads us to track two states:

• f[i]: ways to paint up to post i where posts i-1 and i have different colors
• g[i]: ways to paint up to post i where posts i-1 and i have the same color

For the transitions:

• To achieve different colors at positions i-1 and i (state f[i]), we can come from either state at position i-1. If we had different colors at i-2 and i-1, we have k-1 color choices for post i. If we had same colors at i-2 and i-1, we also have k-1 choices (anything except the color used for the last two posts). So f[i] = (f[i-1] + g[i-1]) * (k-1)

• To achieve same colors at positions i-1 and i (state g[i]), we can only come from the state where i-2 and i-1 had different colors, and we paint post i the same as post i-1. So g[i] = f[i-1]

Starting with the first post, we have k ways to paint it (which we consider as "different" from a non-existent previous post), so f[0] = k and g[0] = 0.

Solution Approach

We implement the solution using dynamic programming with two arrays to track the painting states.

State Definition:

• f[i]: number of ways to paint posts [0..i] where the last two posts have different colors
• g[i]: number of ways to paint posts [0..i] where the last two posts have the same color

Initialization:

• f[0] = k: The first post can be painted with any of the k colors
• g[0] = 0: There's no previous post to have the same color with

State Transition: For each post i from 1 to n-1:

1. Calculate f[i] (last two posts have different colors):

   • We can arrive at this state from either f[i-1] or g[i-1]
   • From both previous states, we have k-1 color choices (any color except the one used for post i-1)
   • Formula: f[i] = (f[i-1] + g[i-1]) * (k-1)

2. Calculate g[i] (last two posts have the same color):

   • We can only arrive at this state from f[i-1] (previous two were different)
   • We paint post i with the same color as post i-1
   • Formula: g[i] = f[i-1]

Final Answer: The total number of ways is f[n-1] + g[n-1], which accounts for all valid painting configurations where the last two posts either have different colors or the same color.

Time Complexity: O(n) - we iterate through all posts once Space Complexity: O(n) - we use two arrays of size n

Example Walkthrough

Let's walk through a small example with n = 3 posts and k = 2 colors (let's call them Red and Blue).

Step 1: Initialize for post 0

• f[0] = 2: We can paint the first post either Red or Blue
• g[0] = 0: No previous post exists to have the same color with

Step 2: Calculate for post 1

• f[1] = (f[0] + g[0]) * (k-1) = (2 + 0) * 1 = 2
  • These represent: (Red, Blue) and (Blue, Red)
• g[1] = f[0] = 2
  • These represent: (Red, Red) and (Blue, Blue)

Step 3: Calculate for post 2

• f[2] = (f[1] + g[1]) * (k-1) = (2 + 2) * 1 = 4
  • From (Red, Blue): we can paint Blue → (Red, Blue, Red)
  • From (Blue, Red): we can paint Red → (Blue, Red, Blue)
  • From (Red, Red): we must paint Blue → (Red, Red, Blue)
  • From (Blue, Blue): we must paint Red → (Blue, Blue, Red)
• g[2] = f[1] = 2
  • From (Red, Blue): we can paint Blue → (Red, Blue, Blue)
  • From (Blue, Red): we can paint Red → (Blue, Red, Red)

Final Answer: f[2] + g[2] = 4 + 2 = 6

The 6 valid ways to paint 3 posts with 2 colors are:

1. Red, Blue, Red
2. Blue, Red, Blue
3. Red, Red, Blue
4. Blue, Blue, Red
5. Red, Blue, Blue
6. Blue, Red, Red

Notice how we avoid having three consecutive posts with the same color (Red, Red, Red or Blue, Blue, Blue would be invalid).

Solution Implementation

Time and Space Complexity

The time complexity is O(n) where n is the number of fence posts. The algorithm uses a single for loop that iterates from index 1 to n-1, performing constant time operations in each iteration (arithmetic operations and array assignments).

The space complexity is O(n) where n is the number of fence posts. The algorithm creates two arrays f and g, each of size n, to store intermediate results. Therefore, the total space used is 2n, which simplifies to O(n).

Common Pitfalls

1. Incorrect State Definition Leading to Triple Consecutive Colors

A common mistake is misunderstanding what the states represent, particularly thinking that same[i] means "all posts up to i have the same color." This would violate the constraint of not having three consecutive posts with the same color.

Wrong interpretation:

# INCORRECT: This doesn't prevent three consecutive same colors
same[i] = same[i-1]  # Wrong! This would allow unlimited consecutive same colors

Correct interpretation: The state same[i] specifically means posts i-1 and i have the same color (not all posts). The transition same[i] = diff[i-1] ensures we can only have at most two consecutive posts with the same color, as we're coming from a state where the previous two were different.

2. Space Optimization Confusion

When optimizing space from O(n) to O(1), a common pitfall is incorrectly updating variables in the wrong order:

Incorrect space-optimized version:

def numWays(self, n: int, k: int) -> int:
    if n == 0: return 0
    if n == 1: return k
  
    diff = k
    same = 0
  
    for i in range(1, n):
        diff = (diff + same) * (k - 1)  # Wrong! diff is modified before being used for same
        same = diff  # This uses the NEW diff value, not the previous one
  
    return diff + same

Correct space-optimized version:

def numWays(self, n: int, k: int) -> int:
    if n == 0: return 0
    if n == 1: return k
  
    diff = k
    same = 0
  
    for i in range(1, n):
        prev_diff = diff  # Store the previous value
        diff = (diff + same) * (k - 1)
        same = prev_diff  # Use the stored previous value
  
    return diff + same

3. Missing Edge Cases

Forgetting to handle edge cases when n = 0 or n = 1 can cause array index errors or incorrect results:

Problem scenario:

# Without edge case handling
diff[1] = (diff[0] + same[0]) * (k - 1)  # Crashes when n = 1 (index out of bounds)

Solution: Always check for n = 0 and n = 1 cases before entering the main loop, as these don't follow the general recurrence relation.

4. Overflow in Large Inputs

For very large values of n and k, the result can exceed integer limits. While Python handles big integers automatically, in other languages you might need modulo arithmetic:

For languages with integer overflow:

MOD = 10**9 + 7  # Common modulo value in competitive programming
diff[i] = ((diff[i-1] + same[i-1]) * (k-1)) % MOD
same[i] = diff[i-1] % MOD