We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Paint House IV

Number: 3737

Difficulty: Medium

Paid? No

Companies: Bloomberg

Problem Description

Given an even integer n and a 2D array cost of size n×3 (where cost[i][j] is the cost to paint house i with color j+1), paint all n houses so that: • No two adjacent houses have the same color. • For every i, the house at index i and the house at index n–1–i (i.e. houses equidistant from the ends) are painted in different colors. Return the minimum total cost to do so.

For example, for n = 4 and cost = [[3,5,7], [6,2,9], [4,8,1], [7,3,5]], one optimal solution is to paint the houses with colors [1, 2, 3, 2] (using 1-indexed color labels) with total cost 9. This assignment satisfies that adjacent houses have different colors and house 0 and house 3, which are symmetric, use different colors; similarly for houses 1 and 2.

Key Insights

  • The two conditions impose two kinds of restrictions: • “Adjacent” restriction: consecutive houses in the row (from index 0 to n–1) must have different colors. • “Symmetric” restriction: house i and house n–1–i (equidistant from the ends) must not share the same color.
  • Since n is even we may “pair” the houses as (i, n–1–i) for i from 0 to n/2 – 1.
  • Within each pair the two colors must be different.
  • In the overall row the left‐side houses (from indices 0 to n/2 – 1) form an ordered sequence (with their own adjacent rule) and the “paired” right–side houses (indices n/2 to n–1) are also “ordered” (although in reverse relative to the pairing). By “reindexing” the right half (via reversal) the adjacent “right” constraint can be enforced similarly.
  • A key idea is to combine the pair’s constraints with the adjacent restrictions from the two halves by “merging” the two halves in a single DP that processes the pairs in an order chosen so that both “left‐adjacent” (in natural order) and “right–adjacent” (in the reversed order) constraints are enforced.
  • In our solution we define m = n/2 and “pair” house i (from the left half) with house n–1–i (from the right half). Then we set up a DP over pairs (indexed by i = 0 … m–1) with a state representing (l, r) – the chosen colors for the left house and its paired right house. The local “pair” constraint (l ≠ r) is obvious.
  • The tricky part is that while the left half appears in natural order (houses 0, 1, …, m–1) so that for consecutive pairs we must enforce left[i+1] ≠ left[i], the right half in the final row is ordered in the reverse of the pair index. (Because the right house for pair i is actually house n–1–i, and as i increases these indices decrease.) By “reversing” the order on the right side we see that the right adjacent condition becomes: for consecutive pairs (when considered in the reversed order) the colors must differ. In our combined DP we end up “coupling” the pair i with a neighbor on the left in the left sequence and with a neighbor on the right in the reversed (i.e. natural) order of the right half. With a re–indexing (defining the pair state at index i corresponding to left house i and right house at index n–1–i) the right side adjacent condition becomes: if two pairs i and i+1 in the DP correspond to right indices j and j–1 in the final arrangement then we must require that the color chosen for pair i (which eventually “lands” at position j) is different from the color chosen for pair i+1 (landing at position j–1). Thus, we impose in the DP for a transition from pair i to pair i+1 that: • left[i+1] must differ from left[i] (for the left side adjacent rule) • right[i+1] must differ from right[i] (which, after re–ordering, is exactly the required condition for the right half)
  • Finally, note that the “middle boundary” (between house m–1 and house m) is automatically satisfied since for pair m–1 (the last pair) the left house and its paired right house are adjacent.
  • Thus the overall recurrence for pair i (state (x,y) for left and right colors) is: • Base case: dp[0][x][y] = cost[0][x] + cost[n–1][y] for any x and y with x ≠ y. • Transition (for i from 0 to m–2): from state (x,y) at pair i to state (x', y') for pair i+1 if: – x' ≠ x (left adjacent constraint) – y' ≠ y (right adjacent constraint, when thought in reversed order) – x' ≠ y' (symmetric (pair) constraint) Then add cost = cost[i+1][x'] + cost[n–1–(i+1)][y'].
  • Finally, the answer is the minimum over dp[m–1][x][y] for all pairs.

Space and Time Complexity

Time Complexity: O(m × 6 × 6) where m = n/2. In worst case O(n) overall. Space Complexity: O(m × 6) states (we store DP for m pairs and at most 6 valid (left, right) color combinations per pair).

Solution

We solve the problem by “pairing” house i (from the left half) with house n–1–i (from the right half). For each pair we need to pick two different colors. In addition, the selection for consecutive pairs must obey: • For the left half, the color chosen for pair i+1 must differ from that chosen for pair i. • For the right half, because the houses appear in reversed order, the color chosen for the right side in pair i+1 (which will ultimately come later in the row) must differ from that chosen for pair i. We define a DP state dp[i][x][y] representing the minimum cost to process pairs 0..i such that for the i-th pair we painted the left house with color x and the right house with color y (with x ≠ y). The cost contributed from the i-th pair is cost[i][x] for the left house (i) plus cost[n–1–i][y] for the right house. For i = 0, initialize dp[0][x][y] = cost[0][x] + cost[n–1][y] for all x ≠ y. Then for each pair i (from 0 to m–2), for each permitted (x, y) choice and for each next pair choice (x', y') that satisfies: – x' ≠ x (left adjacent) – y' ≠ y (right adjacent, following the reversed order requirement) – x' ≠ y' (symmetric pair constraint) we update: dp[i+1][x'][y'] = min(dp[i+1][x'][y'], dp[i][x][y] + cost[i+1][x'] + cost[n–1–(i+1)][y']). The answer is the minimum dp[m–1][x][y] over all x, y.

A couple of important “gotchas”: • The fact that the right houses appear in reverse order relative to the pair index means that the adjacent condition for the right half is “flipped”. In our DP we enforce the condition y' ≠ y which is exactly correct when you do the re–indexing. • There are only 3 colors and in each pair the two colors must differ so only 6 combinations are valid. This keeps the state small.

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java. In all solutions color indices are assumed to be 0, 1, 2 corresponding to the three colors.

#!/usr/bin/env python3
import sys
import math

def minCost(n, cost):
    m = n // 2
    # dp[i] will be a dictionary with key (l, r) for left and right colors of pair i,
    # and value = minimal cost.
    dp = [{} for _ in range(m)]
    # initialize for pair 0: house 0 and house n-1.
    for left_color in range(3):
        for right_color in range(3):
            if left_color == right_color:
                continue
            dp[0][(left_color, right_color)] = cost[0][left_color] + cost[n-1][right_color]
    # Process subsequent pairs i = 1 .. m-1
    for i in range(1, m):
        dp[i] = {}
        left_house_index = i        # house from left half
        right_house_index = n - 1 - i # paired right house
        for (prev_left, prev_right), prev_cost in dp[i-1].items():
            for new_left in range(3):
                # left adjacent constraint: new_left != prev_left
                if new_left == prev_left:
                    continue
                for new_right in range(3):
                    # symmetric constraint for current pair and right adjacent in reversed order:
                    if new_left == new_right or new_right == prev_right:
                        continue
                    curr_cost = prev_cost + cost[left_house_index][new_left] + cost[right_house_index][new_right]
                    key = (new_left, new_right)
                    if key not in dp[i] or curr_cost < dp[i][key]:
                        dp[i][key] = curr_cost
    # answer is minimum value in dp[m-1]
    return min(dp[m-1].values())

# Example usage:
if __name__ == "__main__":
    # Example 1:
    n = 4
    cost = [[3,5,7],[6,2,9],[4,8,1],[7,3,5]]
    print(minCost(n, cost))  # Expected output: 9
← Back to All Questions