Taro Logo

Paint Fence

Medium
Asked by:
Profile picture
62 views
Topics:
Dynamic Programming

You are painting a fence consisting of n posts. You have k different colors available.

Each post must be painted such that no more than two adjacent fence posts have the same color.

Given the two integers n and k, return the number of ways you can paint the fence.

Example 1:

Input: n = 3, k = 2
Output: 6
Explanation:
All possible ways are:
post1  post2  post3      
 ----   ----   ----       
  1      1      2       
  1      2      1       
  1      2      2       
  2      1      1        
  2      1      2
  2      2      1

Example 2:

Input: n = 1, k = 1
Output: 1

Example 3:

Input: n = 7, k = 2
Output: 42

Constraints:

  • 1 <= n <= 50
  • 1 <= k <= 100

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. What are the constraints on the number of fences (n) and the number of colors (k)?
  2. Can 'n' or 'k' be zero? What should I return in those cases?
  3. Are 'n' and 'k' integers? Can they be negative?
  4. If 'k' is 1 and 'n' is greater than 2, is there a valid coloring? What should I return?
  5. Are we only interested in the number of possible ways to paint the fence, or do we need to return the actual valid colorings?

Brute Force Solution

Approach

The brute force approach to the paint fence problem is simple: we'll try every single possible way to paint the fence. This means exploring all combinations of colors for each section of the fence, ensuring we follow the rule about not having too many adjacent sections with the same color.

Here's how the algorithm would work step-by-step:

  1. Start by considering the first section of the fence and try painting it each color that is available to us.
  2. For each color choice made on the first section, move on to the second section of the fence and again try every available color.
  3. Before confirming the color choice for the second section, make sure it doesn't violate the rule about adjacent fence sections.
  4. Continue painting the fence section by section, always trying all available colors for the current section and always checking for rule violations.
  5. If at any point a color choice causes a rule violation, discard it and try the next color.
  6. If we reach the end of the fence without violating any rules, we have a valid painting.
  7. Repeat this entire process, from the first section, to explore all possible valid paintings.
  8. Count all the valid paintings found.

Code Implementation

def paint_fence_brute_force(number_of_posts, number_of_colors):
    if number_of_posts == 0:
        return 0

    valid_combinations_count = 0

    def is_valid_combination(fence):
        # Check for rule violations.
        for i in range(len(fence) - 2):
            if fence[i] == fence[i + 1] == fence[i + 2]:
                return False
        return True

    def generate_combinations(current_fence):
        nonlocal valid_combinations_count

        if len(current_fence) == number_of_posts:
            # Base case: fence is complete, validate it.
            if is_valid_combination(current_fence):
                valid_combinations_count += 1
            return

        # Explore all available color choices.
        for color_index in range(number_of_colors):
            new_fence = current_fence + [color_index]

            # Recursively paint the rest of the fence.
            generate_combinations(new_fence)

    generate_combinations([])
    return valid_combinations_count

Big(O) Analysis

Time Complexity
O(k^n) – The brute force approach explores every possible combination of colors for each of the n fence sections. For each section, we have k color choices. This leads to a branching factor of k at each of the n sections. Thus, the total number of possible paintings we explore is k * k * ... * k (n times), which is k^n. Therefore, the time complexity is O(k^n).
Space Complexity
O(N) – The brute force approach uses recursion to explore all possible color combinations. In the worst-case scenario, the depth of the recursion can go as deep as the number of fence sections, N, where N is the number of fence sections. Each recursive call adds a new frame to the call stack to store the current state (the fence section being painted). Thus, the auxiliary space required is proportional to the maximum depth of the recursion, which is N. This leads to a space complexity of O(N).

Optimal Solution

Approach

The key to efficiently painting the fence is to realize we only need to track the last two fence post colors. Instead of exploring every painting combination, we can focus on how many ways we can paint the current post the same or a different color than the previous post and build our result based on this.

Here's how the algorithm would work step-by-step:

  1. Start by thinking about the first two fence posts. The first post can be painted in any of the available colors.
  2. For the second post, we have two options: paint it the same color as the first, or a different color.
  3. Now, when we move to the third post, consider how the previous two posts were colored. If the previous two posts have different colors, we can paint the current post any of the available colors.
  4. If the previous two posts have the same color, we must paint the current post a different color.
  5. Keep track of the number of ways you can paint the fence such that the last two posts are the same color and the number of ways the last two are different colors.
  6. As you move from one post to the next, update these counts based on the rules for the current post.
  7. At the end, add the number of ways the last two posts are the same color and the number of ways the last two posts are different colors. This is the total number of ways to paint the fence.

Code Implementation

def paint_fence(number_of_posts, number_of_colors):
    if number_of_posts == 0:
        return 0

    # Initialize the possibilities for first two posts.
    same_color_ways = 0
    different_color_ways = number_of_colors

    for i in range(1, number_of_posts):
        # Count ways to paint the current post same or diff.
        current_same_color = different_color_ways

        # If the previous two posts are different colors,
        # the current post can be any color.
        current_different_color = (same_color_ways + different_color_ways) * (number_of_colors - 1)

        # Update for the next iteration
        same_color_ways = current_same_color
        different_color_ways = current_different_color

    # Total ways are sum of same and diff colors.
    return same_color_ways + different_color_ways

Big(O) Analysis

Time Complexity
O(n) – The solution iterates through the fence posts once, from the third post up to the nth post. Inside the loop, it performs a constant number of calculations to update the counts of 'same' and 'different' color combinations based on the previous two posts. Since the number of operations inside the loop is constant and the loop runs (n-2) times, the time complexity is directly proportional to the number of fence posts, n. Therefore, the overall time complexity is O(n).
Space Complexity
O(1) – The provided approach focuses on iteratively updating counts of painting possibilities. Specifically, it tracks the number of ways the last two posts are the same color and the number of ways they are different. These counts are stored in a fixed number of variables, independent of the number of fence posts (N). Therefore, the auxiliary space required remains constant, resulting in O(1) space complexity.

Edge Cases

n = 0 (No fences)
How to Handle:
Return 0 because there are no ways to paint no fences.
k = 0 (No colors)
How to Handle:
Return 0 because there are no colors to paint the fences with if n > 0 and if n = 0 it will be handled by the n=0 edge case.
n = 1 (One fence)
How to Handle:
Return k because there are k possible colors for the one fence.
k = 1 and n > 2 (One color, more than two fences)
How to Handle:
Return 0, as you can't have more than two fences in a row painted with the same color if k = 1 and n > 2.
Integer overflow when calculating the number of ways
How to Handle:
Use long data type to handle larger results, or use modulo operation if the problem specifies a modulo.
Large n (number of fences) affecting memory usage and performance
How to Handle:
The iterative dynamic programming approach efficiently uses constant space since it only needs to store the last two values.
k = 1 (Only one color) and n = 2
How to Handle:
Return 1 because the two fences must be the same color.
k > n (More colors than fences)
How to Handle:
The general formula handles this correctly as the 'different' case still calculates correctly given that k > n.