Paint Fence - Practice Coding Problems

Paint Fence - Problem

Dynamic Programming Medium

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.

Input & Output

Example 1 — Basic Case

$ Input: n = 3, k = 2

› Output: 6

💡 Note: With 3 posts and 2 colors, we can paint: RRG, RGR, RGG, GRR, GRG, GGR (6 ways total, avoiding 3 consecutive same colors)

Example 2 — Single Post

$ Input: n = 1, k = 1

› Output: 1

💡 Note: With 1 post and 1 color, there's only 1 way to paint it

Example 3 — Edge Case

$ Input: n = 3, k = 1

› Output: 0

💡 Note: With only 1 color and 3 posts, we'd have 3 consecutive same colors, which violates the rule

Constraints

1 ≤ n ≤ 50
1 ≤ k ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

n=3 posts, k=2 colors (Red, Green)

Constraint

No 3 consecutive posts can have the same color

Output

Count total valid painting ways = 6

Key Takeaway

🎯 Key Insight: Track same vs different color patterns to avoid 3+ consecutive same colors efficiently

Asked in

G Google 25 f Facebook 20 a Amazon 15

The key insight is to track two patterns: posts ending with same color vs different color than previous post. The optimal bottom-up DP approach uses recurrence relations to build the solution iteratively. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Recursion	O(k^n)	O(n)	Generate all possible color combinations and count valid ones
Memoization (Top-Down DP)	O(n × k)	O(n × k)	Use recursion with caching to avoid redundant calculations
Bottom-Up Dynamic Programming	O(n)	O(1)	Track patterns: posts with same color vs different color than previous

Brute Force Recursion — Algorithm Steps

For each post, try all k colors
Recursively solve for remaining posts
Count combinations that don't have 3 consecutive same colors

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin with first post, try all k colors

Recurse

For each color choice, recursively solve remaining posts

Count

Count valid combinations without 3 consecutive same colors

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>

int backtrack(int pos, int lastColor, int sameCount, int n, int k) {
    if (pos == n) {
        return 1;
    }
    
    int total = 0;
    for (int color = 0; color < k; color++) {
        if (color == lastColor) {
            if (sameCount < 2) {
                total += backtrack(pos + 1, color, sameCount + 1, n, k);
            }
        } else {
            total += backtrack(pos + 1, color, 1, n, k);
        }
    }
    return total;
}

int solution(int n, int k) {
    if (n == 0 || k == 0) {
        return 0;
    }
    return backtrack(0, -1, 0, n, k);
}

int main() {
    int n, k;
    scanf("%d", &n);
    scanf("%d", &k);
    
    int result = solution(n, k);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k^n)

For each of n posts, we try k colors, leading to k^n combinations

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth is n levels deep

⚡ Linearithmic Space

52.0K Views

Medium Frequency

~25 min Avg. Time

867 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler