We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Paint Fence

Number: 276

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

Given n fence posts and k different colors, determine the number of ways to paint the fence such that each post is painted exactly one color and no three consecutive posts have the same color.

Key Insights

  • Use dynamic programming to break the problem into subproblems.
  • Define two states:
    • Ways ending with two posts of the same color.
    • Ways ending with two posts of different colors.
  • The transition for the "same" state is only possible if the previous state ended with two different colors.
  • The "different" state can be achieved by painting a new color that is different from the previous post in both states.
  • The final answer is the sum of these two states.

Space and Time Complexity

Time Complexity: O(n) – We compute the result by iterating through each post. Space Complexity: O(1) – Only a fixed number of variables are used for state transitions.

Solution

The strategy is to simulate the painting process post by post while tracking two values:

  1. same: Number of ways where the last two posts are painted with the same color.
  2. diff: Number of ways where the last two posts are painted with different colors.

For the first post, the total ways is k. For the second post:

  • same = k (each pair where both posts get the same color),
  • diff = k * (k - 1) (different colors for first and second post).

For posts from the third onward, update by:

  • same[i] = diff[i-1] because only a configuration that ended with two different colors can add a post with the same color as the previous one.
  • diff[i] = (same[i-1] + diff[i-1]) * (k - 1) since any valid configuration can add a different color post.

By iterating up to n, the final result will be same + diff.

Code Solutions

# Python solution for the Paint Fence problem
def numWays(n: int, k: int) -> int:
    # Base cases:
    if n == 0:
        return 0
    if n == 1:
        return k

    # For n >= 2, initialize:
    # same: ways ending with two posts of same color
    # diff: ways ending with two posts with different colors
    same = k  # both posts have the same color
    diff = k * (k - 1)  # the two posts have different colors

    # Iterate from the 3rd post to the nth post
    for i in range(3, n + 1):
        # New same can only come from previous diff (to avoid three in a row same)
        new_same = diff
        # New different can come from any configuration followed by a different color
        new_diff = (same + diff) * (k - 1)
        same, diff = new_same, new_diff  # update states

    # Total ways is the sum of finishing in either same or diff state
    return same + diff

# Example usage:
print(numWays(3, 2))  # Expected output: 6
← Back to All Questions