Paint House - Practice Coding Problems

Paint House - Problem

There is a row of n houses, where each house can be painted one of three colors: red, blue, or green.

The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by an n x 3 cost matrix costs. For example, costs[0][0] is the cost of painting house 0 with the color red; costs[1][2] is the cost of painting house 1 with color green, and so on.

Return the minimum cost to paint all houses.

Input & Output

Example 1 — Basic Three Houses

$ Input: costs = [[17,2,17],[16,16,5],[14,3,19]]

› Output: 10

💡 Note: Paint house 0 blue (cost 2), house 1 green (cost 5), house 2 blue (cost 3). Total cost = 2 + 5 + 3 = 10.

Example 2 — Single House

$ Input: costs = [[7,6,2]]

› Output: 2

💡 Note: Only one house, so paint it with the cheapest color (green, cost 2).

Example 3 — Two Houses

$ Input: costs = [[5,8,6],[19,14,13]]

› Output: 18

💡 Note: Paint house 0 red (cost 5), house 1 green (cost 13). Total cost = 5 + 13 = 18.

Constraints

1 ≤ costs.length ≤ 100
costs[i].length == 3
1 ≤ costs[i][j] ≤ 20

Visualization

Tap to expand

Understanding the Visualization

Input

Cost matrix with 3 colors per house

Constraint

Adjacent houses cannot have same color

Output

Minimum total cost

Key Takeaway

🎯 Key Insight: Each house's optimal cost depends only on avoiding the previous house's color

Asked in

F Facebook 45 a Amazon 35 G Google 30 M Microsoft 25

The key insight is that this is a dynamic programming problem where each house's optimal cost depends only on the previous house. The space-optimized DP approach is optimal with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Memoization (Top-Down DP)	O(n)	O(n)	Cache recursive results to avoid recalculation
2D Dynamic Programming	O(n)	O(n)	Build DP table tracking minimum cost for each house and color
Brute Force Recursion	O(3ⁿ)	O(n)	Try all possible color combinations recursively
Space-Optimized DP	O(n)	O(1)	Optimize space by only keeping previous house costs

Memoization (Top-Down DP) — Algorithm Steps

Use recursion with memoization
Cache results for (house, prev_color) pairs
Return cached result if already computed

Code -

solution.c — C

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

int memo[1000][4];
int memoSet[1000][4];

int paintHouse(int** costs, int n, int house, int prevColor) {
    if (house == n) {
        return 0;
    }
    
    int memoIdx = prevColor + 1;
    if (memoSet[house][memoIdx]) {
        return memo[house][memoIdx];
    }
    
    int minCost = INT_MAX;
    for (int color = 0; color < 3; color++) {
        if (color != prevColor) {
            int cost = costs[house][color] + paintHouse(costs, n, house + 1, color);
            if (cost < minCost) {
                minCost = cost;
            }
        }
    }
    
    memo[house][memoIdx] = minCost;
    memoSet[house][memoIdx] = 1;
    return minCost;
}

int solution(int** costs, int n) {
    memset(memoSet, 0, sizeof(memoSet));
    return paintHouse(costs, n, 0, -1);
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    int** costs = NULL;
    int n = 0;
    char* ptr = line + 1;
    while (*ptr && *ptr != ']') {
        costs = realloc(costs, (n + 1) * sizeof(int*));
        costs[n] = malloc(3 * sizeof(int));
        if (*ptr == '[') ptr++;
        sscanf(ptr, "%d,%d,%d", &costs[n][0], &costs[n][1], &costs[n][2]);
        n++;
        while (*ptr && *ptr != ']') ptr++;
        if (*ptr == ']') ptr++;
        if (*ptr == ',') ptr++;
    }
    
    printf("%d\n", solution(costs, n));
    for (int i = 0; i < n; i++) free(costs[i]);
    free(costs);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each of the n×3 states is computed once and cached

✓ Linear Growth

Space Complexity

O(n)

Memoization table stores n×3 states plus recursion stack

⚡ Linearithmic Space

89.6K Views

High Frequency

~15 min Avg. Time

2.8K 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