LeetCode 276: Paint Fence Solution in Python – A Step-by-Step Guide

What Is LeetCode 276: Paint Fence?

In LeetCode 276: Paint Fence, you’re given an integer n (number of fence posts) and an integer k (number of colors), and your task is to find the number of ways to paint the fence such that no more than two adjacent posts have the same color. For example, with n = 3 and k = 2, there are 6 ways to paint it. This problem tests your ability to model sequential choices with constraints, connecting to concepts in LeetCode 256: Paint House.

Problem Statement

• Input: Two integers n (posts) and k (colors).
• Output: An integer—the number of ways to paint the fence.
• Rules:
• No more than two adjacent posts can have the same color.
• Each post must be painted with one of k colors.
• Result fits within 32-bit integer.

Constraints

• 1 <= n <= 50
• 1 <= k <= 10⁵

Examples

• Input: n = 3, k = 2
• Output: 6 (e.g., [1,1,2], [1,2,1], [1,2,2], [2,1,1], [2,1,2], [2,2,1])
• Input: n = 1, k = 1
• Output: 1 (Only [1])
• Input: n = 2, k = 2
• Output: 4 ([1,1], [1,2], [2,1], [2,2])

Understanding the Problem: Painting with Rules

To solve LeetCode 276: Paint Fence in Python, we need to count the ways to paint n posts with k colors, ensuring no three consecutive posts are the same color. A naive approach—trying all combinations—is O(k^n), exponential and impractical for n up to 50. Instead, we’ll use:

• Best Solution (DP with Constant Space): O(n) time, O(1) space—fast and optimal.
• Alternative Solution (DP with Array): O(n) time, O(n) space—clear but uses more memory.

Let’s start with the constant-space DP solution, explained in a beginner-friendly way.

Best Solution: DP with Constant Space

Why This Is the Best Solution

The constant-space DP approach is the top choice for LeetCode 276 because it’s efficient—O(n) time, O(1) space—and cleverly tracks only the last two states to compute the total ways, avoiding a full array. It uses the insight that each post’s painting depends only on the previous two, making it both fast and memory-light. It’s like painting post-by-post with a smart tally—brilliant and sleek!

How It Works

Think of this as a painting tally:

• Step 1: Define States:
• same: Ways to paint up to current post with last two same color.
• diff: Ways to paint up to current post with last two different colors.
• Step 2: Base Cases:
• n=1: k ways (all diff).
• n=2: k (same) + k*(k-1) (diff).
• Step 3: Transition:
• For each post i > 2:
• New same = old diff * 1 (add same color).
• New diff = (old same + old diff) * (k-1) (add different color).
• Step 4: Total Ways:
• Return same + diff.
• Step 5: Why It Works:
• Tracks all possibilities with minimal variables.
• Avoids three-in-a-row by design.

It’s like keeping a running score of painting options!

Step-by-Step Example

Example: n = 3, k = 2

• n=1: same = 0, diff = 2 (2 ways)
• n=2:
• same = diff * 1 = 2 * 1 = 2 (e.g., [1,1], [2,2])
• diff = (same + diff) * (k-1) = (0 + 2) * 1 = 2 (e.g., [1,2], [2,1])
• n=3:
• new_same = diff * 1 = 2 * 1 = 2 (e.g., [1,2,2], [2,1,1])
• new_diff = (same + diff) * (k-1) = (2 + 2) * 1 = 4 (e.g., [1,1,2], [1,2,1], [2,2,1], [2,1,2])
• Total: same + diff = 2 + 4 = 6
• Result: 6

Code with Detailed Line-by-Line Explanation

Copy codeclass Solution:
    def numWays(self, n: int, k: int) -> int:
        # Base cases
        if n == 1:
            return k
        if n == 2:
            return k * k

        # Initialize for n=2
        same, diff = k, k * (k - 1)

        # Iterate for n > 2
        for i in range(3, n + 1):
            new_same = diff  # Last two same = last diff * 1
            new_diff = (same + diff) * (k - 1)  # Last two diff = total * (k-1)
            same, diff = new_same, new_diff

        return same + diff

• Lines 3-6: Handle n=1 (k) and n=2 (k*k).
• Line 9: Init for n=2: same = k, diff = k*(k-1).
• Lines 12-15: Loop for n > 2:
• New same = old diff (add same color).
• New diff = (old same + old diff) * (k-1) (add different color).
• Line 17: Return total ways.
• Time Complexity: O(n)—linear pass.
• Space Complexity: O(1)—two variables.

This is like a painting-score wizard—fast and lean!

Alternative Solution: DP with Array

Why an Alternative Approach?

The DP with array approach—O(n) time, O(n) space—uses arrays to store same and diff for each post, offering a clear view of the state transitions. It’s more intuitive for understanding DP but uses more space than needed. It’s like keeping a full log of painting options—vivid but heavier!

How It Works

Track states with arrays:

• Step 1: same[i] = ways up to i with last two same.
• Step 2: diff[i] = ways up to i with last two different.
• Step 3: Fill arrays with transitions.
• Step 4: Return total at n.

Step-by-Step Example

Example: n = 3, k = 2

• Init: same = [0,0,0,0], diff = [0,2,0,0]
• i=2:
• same[2] = diff[1] = 2
• diff[2] = (same[1] + diff[1]) * 1 = (0 + 2) * 1 = 2
• i=3:
• same[3] = diff[2] = 2
• diff[3] = (same[2] + diff[2]) * 1 = (2 + 2) * 1 = 4
• Total: same[3] + diff[3] = 2 + 4 = 6
• Result: 6

Code for DP Array Approach

Copy codeclass Solution:
    def numWays(self, n: int, k: int) -> int:
        if n == 1:
            return k
        if n == 2:
            return k * k

        same = [0] * (n + 1)
        diff = [0] * (n + 1)
        diff[1] = k

        for i in range(2, n + 1):
            same[i] = diff[i-1]
            diff[i] = (same[i-1] + diff[i-1]) * (k - 1)

        return same[n] + diff[n]

• Time Complexity: O(n)—linear pass.
• Space Complexity: O(n)—two arrays.

It’s a detailed painting tracker—clear but bulkier!

Comparing the Two Solutions

• DP with Constant Space (Best):
• Pros: O(n) time, O(1) space, fast and lean.
• Cons: Less visual state tracking.
• DP with Array (Alternative):
• Pros: O(n) time, O(n) space, explicit states.
• Cons: Uses more memory.

Constant-space DP wins for efficiency.

Additional Examples and Edge Cases

• n=1, k=3: 3.
• n=4, k=1: 0 (can’t avoid 3 in a row).
• n=2, k=3: 9.

Both handle these, but constant-space is leaner.

Complexity Breakdown

• Constant Space DP: Time O(n), Space O(1).
• Array DP: Time O(n), Space O(n).

Constant-space DP is the clear choice.

Key Takeaways

• Constant Space DP: Tally smart—efficient!
• Array DP: Track all—clear!
• Python: Loops and logic shine—see [Python Basics](/python/basics).
• Painting: Constraints shape creativity.

Final Thoughts: Color the Fence

LeetCode 276: Paint Fence in Python is a dynamic programming delight. The constant-space DP solution offers speed and elegance, while the array-based approach provides a tangible baseline. Want more DP challenges? Try LeetCode 256: Paint House or LeetCode 198: House Robber. Ready to paint? Head to Solve LeetCode 276 on LeetCode (premium) and splash those colors today!