Painting the Fence

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Count ways to paint n fences with k colors where no more than 2 consecutive fences have the same color.

Algorithm

1same[i] = ways where last two have same color.
2diff[i] = ways where last two have different color.
3same[i] = diff[i-1]. diff[i] = (same[i-1] + diff[i-1]) * (k-1).
4Answer = same[n] + diff[n].

Common Pitfalls

•No 3 consecutive same. After same, must differ. After diff, can either (but not 3rd same).

Painting the Fence.java

Java


// Approach: DP. Track same (last two posts same color) and diff (different color).
// same[i] = diff[i-1], diff[i] = total[i-1] * (k-1). Total = same + diff.
// Time: O(n) Space: O(1)
class Solution {

    int countWays(int n, int k) {
        // There are k ways to color first post
        int total = k;

        // There are 0 ways for single post to
        // violate (same color_ and k ways to
        // not violate (different color)
        int same = 0, diff = k;

        // Fill for 2 posts onwards
        for (int i = 2; i <= n; i++) {
            // Current same is same as previous diff
            same = diff;

            // We always have k-1 choices for next post
            diff = ((int) total * (k - 1));

            // Total choices till i.
            total = (same + diff);
        }
        
        return total;
    }
}

Was this solution helpful?