Skip to main content

276. Paint Fence

medium

Paint n fence posts with k colors so that no three consecutive posts share a color. A two-state recurrence — same-as-prev vs different — collapsing to two scalars.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

You are painting a fence of n posts with k different colors. You must paint the posts following these rules: Every post must be painted exactly one color. There cannot be three or more consecutive posts with the same color. Given the two integers n and k, return the number of ways you can paint the fence.

Constraints

  • 1 <= n <= 50
  • 1 <= k <= 10^5
  • The testcases are generated such that the answer is in the range [0, 2^31 - 1] for the given n and k.

Examples

Example 1

Input
n = 3, k = 2
Output
6

Explanation: All the possibilities for the 6 combinations are shown.

Example 2

Input
n = 1, k = 1
Output
1

Example 3

Input
n = 7, k = 2
Output
42

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Track two states per post: same as previous color, or different from previous color.

Hint 2

same[i] = diff[i-1]. diff[i] = (same[i-1] + diff[i-1]) * (k - 1).

Hint 3

Total ways for post i = same[i] + diff[i]. Base case post 1: same = 0, diff = k (or treat post 1 as both choices).

Solution approach

Reveal approach

Two-state DP. Let same be the number of ways to paint up to the current post such that the current post equals the previous, and diff be the number where it differs. Initialize for post 2: same = k (paint both posts the same color, k options), diff = k * (k - 1) (paint post 1 any color, post 2 any of the remaining k - 1). Iterate from post 3 to n: new_same = diff (you can only extend with same if the previous pair was a diff — otherwise you would create three in a row); new_diff = (same + diff) * (k - 1) (any previous pair can be followed by any of the k - 1 other colors). Return same + diff. Handle n = 1 as k. O(n) time, O(1) space.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • dynamic-programming
  • state-machine
  • combinatorics

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google

Practice these live with InterviewChamp.AI

Drill Paint Fence and DP 1D problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →