Paint Fence

Medium

Google

1 view

Topics:

Dynamic Programming

Let's explore a classic dynamic programming problem.

Suppose you have a fence with n posts and you want to paint it with k different colors. You must paint all the posts such that no more than two adjacent fence posts have the same color. Given the integers n and k, return the number of ways you can paint the fence.

Here's a breakdown of the problem with examples:

Problem Definition: You are given a fence with n posts and k colors to paint it. The constraint is that no more than two adjacent posts can have the same color.
Input: Two integers, n (number of posts) and k (number of colors).
Output: The number of possible ways to paint the fence adhering to the constraint.
Examples:
- n = 3, k = 2: Possible colorings include (color1, color1, color2), (color1, color2, color1), (color1, color2, color2), (color2, color1, color1), (color2, color1, color2), (color2, color2, color1). Thus, the output is 6.
- n = 5, k = 3: You would need to calculate the possible combinations given that no more than two adjacent posts can have the same color.
- n = 2, k = 1: output is 1. The fence would be painted with (color1, color1) which is a valid coloring given the constraints of the problem.
- n = 3, k = 1: output is 0. The fence would be painted with (color1, color1, color1) which is not a valid coloring given the constraints of the problem.

Can you describe an algorithm to solve this problem efficiently? Consider both time and space complexity. Start with a naive approach, and then optimize.

Paint Fence

Medium

Google

1 view

Topics:

Dynamic Programming

Let's explore a classic dynamic programming problem.

Here's a breakdown of the problem with examples:

Problem Definition: You are given a fence with n posts and k colors to paint it. The constraint is that no more than two adjacent posts can have the same color.
Input: Two integers, n (number of posts) and k (number of colors).
Output: The number of possible ways to paint the fence adhering to the constraint.
Examples:
- n = 3, k = 2: Possible colorings include (color1, color1, color2), (color1, color2, color1), (color1, color2, color2), (color2, color1, color1), (color2, color1, color2), (color2, color2, color1). Thus, the output is 6.
- n = 5, k = 3: You would need to calculate the possible combinations given that no more than two adjacent posts can have the same color.
- n = 2, k = 1: output is 1. The fence would be painted with (color1, color1) which is a valid coloring given the constraints of the problem.
- n = 3, k = 1: output is 0. The fence would be painted with (color1, color1, color1) which is not a valid coloring given the constraints of the problem.

Can you describe an algorithm to solve this problem efficiently? Consider both time and space complexity. Start with a naive approach, and then optimize.

Solution

Paint Fence

Naive Solution (Brute Force)

A naive approach to solving the "Paint Fence" problem involves considering all possible color combinations for each fence post. For each post, we iterate through all available colors and recursively explore the subsequent posts. This leads to a combinatorial explosion and is highly inefficient.

For example, if we have n fence posts and k colors, for the first post, we have k choices. For the second post, we also have k choices, and so on. We need to ensure that no more than two adjacent posts have the same color.

This approach will result in a time complexity of O(k^n), where k is the number of colors and n is the number of fence posts, and will exceed time limits.

Optimal Solution (Dynamic Programming)

A more efficient approach utilizes dynamic programming. We can observe that the number of ways to paint the i-th fence depends on the number of ways to paint the (i-1)-th and (i-2)-th fences.

Let same[i] be the number of ways to paint the i-th fence such that it has the same color as the (i-1)-th fence. Let diff[i] be the number of ways to paint the i-th fence such that it has a different color from the (i-1)-th fence.

Then, the total number of ways to paint i fences is same[i] + diff[i].

We can derive the following recurrence relations:

same[i] = diff[i-1] (since the i-th fence must have the same color as the (i-1)-th, the (i-1)-th must have a different color from the (i-2)-th).
diff[i] = (same[i-1] + diff[i-1]) * (k-1) (since the i-th fence must have a different color from the (i-1)-th, the (i-1)-th fence can either have the same color as the (i-2)-th or a different color, and there are k-1 choices for the color of the i-th fence).

Edge Cases

If n = 0, there are 0 ways to paint the fence.
If n = 1, there are k ways to paint the fence.
If k = 1 and n > 2, there are 0 ways to paint the fence, because at least three consecutive posts would have the same color. If k=1 and n <= 2, there is 1 way to paint the fence.

Code (Java)

public int numWays(int n, int k) {
    if (n == 0) return 0;
    if (n == 1) return k;
    if (k == 1 && n > 2) return 0;
    if (k == 1 && n <= 2) return 1;

    int same = k;
    int diff = k * (k - 1);

    for (int i = 3; i <= n; i++) {
        int temp = diff;
        diff = (same + diff) * (k - 1);
        same = temp;
    }

    return same + diff;
}

Code (Python)

def num_ways(n, k):
    if n == 0: return 0
    if n == 1: return k
    if k == 1 and n > 2: return 0
    if k == 1 and n <= 2: return 1

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

    for i in range(3, n + 1):
        temp = diff
        diff = (same + diff) * (k - 1)
        same = temp

    return same + diff

Complexity Analysis

Time Complexity: O(n), as we iterate through the fence posts once.
Space Complexity: O(1), as we only use a constant amount of extra space to store the same and diff values.

Solution

Paint Fence

Naive Solution (Brute Force)

This approach will result in a time complexity of O(k^n), where k is the number of colors and n is the number of fence posts, and will exceed time limits.

Optimal Solution (Dynamic Programming)

A more efficient approach utilizes dynamic programming. We can observe that the number of ways to paint the i-th fence depends on the number of ways to paint the (i-1)-th and (i-2)-th fences.

Then, the total number of ways to paint i fences is same[i] + diff[i].

We can derive the following recurrence relations:

same[i] = diff[i-1] (since the i-th fence must have the same color as the (i-1)-th, the (i-1)-th must have a different color from the (i-2)-th).
diff[i] = (same[i-1] + diff[i-1]) * (k-1) (since the i-th fence must have a different color from the (i-1)-th, the (i-1)-th fence can either have the same color as the (i-2)-th or a different color, and there are k-1 choices for the color of the i-th fence).

Edge Cases

If n = 0, there are 0 ways to paint the fence.
If n = 1, there are k ways to paint the fence.
If k = 1 and n > 2, there are 0 ways to paint the fence, because at least three consecutive posts would have the same color. If k=1 and n <= 2, there is 1 way to paint the fence.

Code (Java)

public int numWays(int n, int k) {
    if (n == 0) return 0;
    if (n == 1) return k;
    if (k == 1 && n > 2) return 0;
    if (k == 1 && n <= 2) return 1;

    int same = k;
    int diff = k * (k - 1);

    for (int i = 3; i <= n; i++) {
        int temp = diff;
        diff = (same + diff) * (k - 1);
        same = temp;
    }

    return same + diff;
}

Code (Python)

def num_ways(n, k):
    if n == 0: return 0
    if n == 1: return k
    if k == 1 and n > 2: return 0
    if k == 1 and n <= 2: return 1

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

    for i in range(3, n + 1):
        temp = diff
        diff = (same + diff) * (k - 1)
        same = temp

    return same + diff

Complexity Analysis

Time Complexity: O(n), as we iterate through the fence posts once.
Space Complexity: O(1), as we only use a constant amount of extra space to store the same and diff values.