LeetCode 276 - Paint Fence

The problem gives us a fence with n posts and k available colors. Every fence post must be painted using exactly one of those colors. The important restriction is that we are not allowed to have three or more consecutive posts painted with the same color.

leetcodemediumdynamic-programming

LeetCode Problem 276

Difficulty: 🟡 Medium
Topics: Dynamic Programming

Solution

Problem Understanding

The problem gives us a fence with n posts and k available colors. Every fence post must be painted using exactly one of those colors. The important restriction is that we are not allowed to have three or more consecutive posts painted with the same color.

We are asked to compute the total number of valid painting combinations.

For example, if n = 3 and k = 2, we can use two colors, such as red and blue. Some arrangements are valid:

  • Red, Red, Blue
  • Red, Blue, Red
  • Blue, Blue, Red

However, arrangements like:

  • Red, Red, Red
  • Blue, Blue, Blue

are invalid because they contain three consecutive posts with the same color.

The input consists of:

  • n, the number of fence posts
  • k, the number of available colors

The output is a single integer representing the number of valid painting configurations.

The constraints are relatively small:

  • 1 <= n <= 50
  • 1 <= k <= 10^5

Although n is small, the number of possible combinations grows exponentially if we try every arrangement directly. This strongly suggests that a brute-force recursive solution would become inefficient, and that dynamic programming is a more suitable approach.

Several edge cases are important:

  • When n = 1, every color is valid, so the answer is simply k.

  • When k = 1, there is only one available color. This means:

  • n = 1 gives 1 valid arrangement.

  • n = 2 gives 1 valid arrangement.

  • n >= 3 gives 0 valid arrangements because three identical consecutive posts would appear.

  • Very large values of k can produce large intermediate counts, so the recurrence relation must be implemented carefully.

Approaches

Brute Force Approach

A straightforward solution is to generate every possible coloring of the fence and check whether it satisfies the constraint.

For each of the n posts, we have k choices. This creates k^n total combinations. We could recursively build every arrangement and reject any configuration where three consecutive posts share the same color.

This approach is correct because it explicitly examines every possible painting arrangement and counts only the valid ones.

However, the time complexity becomes exponential. Even with moderate values of n and k, the number of combinations becomes extremely large. For example:

  • n = 50
  • k = 2

would require exploring 2^50 possibilities, which is infeasible.

The key issue is that many subproblems repeat. For example, the number of valid ways to paint the remaining posts depends only on the recent coloring pattern, not the full history.

Optimal Dynamic Programming Approach

The important observation is that the validity of the next post depends only on the previous two posts.

We can classify valid arrangements into two categories:

  • same, where the last two posts have the same color
  • different, where the last two posts have different colors

This classification is enough to build a recurrence relation.

Suppose we are painting the current post:

  • To end in the same state, the current post must match the previous one. This is only allowed if the previous arrangement ended in different.
  • To end in the different state, the current post must use a different color from the previous post. We can choose any of the k - 1 remaining colors.

This leads to an efficient linear-time dynamic programming solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(k^n) O(n) Recursively generates all possible colorings
Optimal O(n) O(1) Dynamic programming using two running states

Algorithm Walkthrough

  1. Handle the base case where there is only one fence post.

If n == 1, every color is valid, so the answer is simply k. 2. Initialize the states for two fence posts.

For two posts:

  • same = k

Both posts use the same color. There are k ways to choose that color.

  • different = k * (k - 1)

The second post must differ from the first. The first post has k choices, and the second has k - 1 choices. 3. Iterate from the third post onward.

For every new post:

  • The new same value becomes the old different.

This is because we can only create two equal consecutive posts if the previous pair was different.

  • The new different value becomes:

(same + different) * (k - 1)

Regardless of the previous state, we can paint the current post a different color from the previous post. 4. Update the running states after each iteration.

We only need the previous iteration values, so we reuse variables instead of storing an entire DP array. 5. Return the total number of valid arrangements.

The final answer is:

same + different

Why it works

The algorithm maintains a precise invariant:

  • same always stores the number of valid arrangements where the last two posts share the same color.
  • different always stores the number of valid arrangements where the last two posts have different colors.

Every valid arrangement must belong to exactly one of these categories. The transitions preserve the rule that no three consecutive posts can share the same color. Because every valid arrangement is counted exactly once, the recurrence produces the correct total.

Python Solution

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

        same = k
        different = k * (k - 1)

        for _ in range(3, n + 1):
            new_same = different
            new_different = (same + different) * (k - 1)

            same = new_same
            different = new_different

        return same + different

The implementation starts by handling the simplest case where only one fence post exists. In that scenario, every color choice is valid.

The variables same and different represent the two dynamic programming states. For two fence posts:

  • same counts arrangements where both posts match.
  • different counts arrangements where the posts differ.

The loop begins at the third post because the first two posts are already represented by the initial state values.

Inside the loop:

  • new_same becomes the previous different value because only arrangements ending with different colors can safely add one matching color.
  • new_different counts all ways to use a different color from the previous post.

Finally, the solution returns the sum of both states because every valid arrangement ends in either the same or different category.

Go Solution

func numWays(n int, k int) int {
    if n == 1 {
        return k
    }

    same := k
    different := k * (k - 1)

    for i := 3; i <= n; i++ {
        newSame := different
        newDifferent := (same + different) * (k - 1)

        same = newSame
        different = newDifferent
    }

    return same + different
}

The Go implementation follows the exact same recurrence relation as the Python version. Since Go uses explicit variable declarations, the temporary variables newSame and newDifferent are declared inside the loop.

The problem guarantees that the final answer fits within a 32-bit signed integer, so Go's standard int type is sufficient for this problem on LeetCode.

Worked Examples

Example 1

Input:

n = 3, k = 2

Initialization for two posts:

State Value Explanation
same 2 RR, BB
different 2 RB, BR

Now process the third post.

Step new_same new_different Explanation
Post 3 2 4 Matching requires previous different state

After updating:

State Value
same 2
different 4

Final answer:

2 + 4 = 6

Example 2

Input:

n = 1, k = 1

Only one post exists, and there is one available color.

Result:

1

Example 3

Input:

n = 7, k = 2

Initial states:

State Value
same 2
different 2

Process remaining posts:

Post same different
3 2 4
4 4 6
5 6 10
6 10 16
7 16 26

Final answer:

16 + 26 = 42

Complexity Analysis

Measure Complexity Explanation
Time O(n) We process each fence post exactly once
Space O(1) Only a few variables are stored

The algorithm performs a constant amount of work for each post after initialization. Since the loop runs from 3 through n, the total runtime grows linearly with the number of fence posts.

The space complexity remains constant because we only maintain two state variables instead of storing an entire dynamic programming table.

Test Cases

solution = Solution()

assert solution.numWays(3, 2) == 6       # example case
assert solution.numWays(1, 1) == 1       # single post, single color
assert solution.numWays(7, 2) == 42      # larger example

assert solution.numWays(1, 5) == 5       # one post, multiple colors
assert solution.numWays(2, 1) == 1       # two posts can share same color
assert solution.numWays(3, 1) == 0       # three same colors invalid

assert solution.numWays(2, 2) == 4       # all combinations valid for two posts
assert solution.numWays(3, 3) == 24      # multiple colors, larger branching

assert solution.numWays(4, 2) == 10      # verifies recurrence transition
assert solution.numWays(5, 2) == 16      # continued DP progression

assert solution.numWays(50, 2) > 0       # stress test for maximum n
assert solution.numWays(10, 100000) > 0  # stress test for large k
Test Why
n=3, k=2 Validates the main example
n=1, k=1 Smallest possible input
n=7, k=2 Larger recurrence chain
n=1, k=5 Single post handling
n=2, k=1 Two identical posts allowed
n=3, k=1 Three identical posts forbidden
n=2, k=2 Every arrangement valid for two posts
n=3, k=3 Multiple branching possibilities
n=4, k=2 Verifies DP state transitions
n=5, k=2 Ensures recurrence consistency
n=50, k=2 Maximum fence length stress test
n=10, k=100000 Large color count stress test

Edge Cases

One important edge case occurs when n = 1. In this situation, there are no adjacency constraints because only one post exists. A common bug is to apply the recurrence relation immediately without handling this separately. The implementation avoids this issue by returning k directly before any dynamic programming logic begins.

Another critical edge case appears when k = 1. With only one available color, the fence can only be painted validly if there are fewer than three posts. A naive implementation might accidentally allow three identical consecutive posts. The recurrence naturally prevents this because once the algorithm reaches the third post, the different state becomes zero, causing all future valid configurations to disappear.

A third important edge case involves very large values of k. Since k may be as large as 100000, intermediate multiplication results can become large quickly. The recurrence is designed to use integer arithmetic efficiently without unnecessary storage structures. The problem guarantees that the final answer fits within a 32-bit signed integer, so the implementation remains safe within the expected constraints.