Log inSign up
mediumGeeksforGeeksNot Started

Paint House

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on GeeksforGeeks
Lesson

Problem Statement

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.

Return the minimum cost to paint all houses.

### Example 1 - Input: costs = [[17, 2, 17], [16, 16, 5], [14, 3, 19]] - Output: 10 - Explanation: Paint house 0 blue (cost 2), house 1 green (cost 5), house 2 blue (cost 3). Total = 2 + 5 + 3 = 10.

### Example 2 - Input: costs = [[7, 6, 2]] - Output: 2

Constraints:

  • costs.length == n
  • costs[i].length == 3
  • 1 <= n <= 100
  • 1 <= costs[i][j] <= 20

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Formulate finite-state dynamic programming with color constraints.
  • Update state variables simultaneously using temporary variables.
  • Achieve optimal O(1) auxiliary space.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Sequence of items with 3 choices each.
  • No two adjacent items can have the same choice.
  • Cost minimization.

Algorithmic Decision Tree:

  • Maintain 3 variables for red, blue, green.
  • Update simultaneously using previous values.

Connected Patterns:

Paint House IIHouse RobberBest Time to Buy and Sell Stock

1. Recursive Exhaustive Search

Intuition

Recursively try painting each house with a color different from the previous house.

Algorithm

  1. Define solve(house, prevColor).
  2. If house == n, return 0.
  3. Try all colors c in {0, 1, 2} where c != prevColor.
  4. Return costs[house][c] + solve(house + 1, c).
  5. Return min across all valid colorings.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 int solve(int idx, int prevColor, const vector<vector<int>>& costs) {
9 if (idx == costs.size()) return 0;
10 int minCost = 1e9;
11 for (int c = 0; c < 3; ++c) {
12 if (c != prevColor) {
13 minCost = min(minCost, costs[idx][c] + solve(idx + 1, c, costs));
14 }
15 }
16 return minCost;
17 }
18public:
19 int minCost(vector<vector<int>>& costs) {
20 return solve(0, -1, costs);
21 }
22};
23
24int main() {
25 Solution sol;
26 vector<vector<int>> costs = {{17, 2, 17}, {16, 16, 5}, {14, 3, 19}};
27 cout << "Min Cost: " << sol.minCost(costs) << endl;
28 return 0;
29}

Time & Space Complexity

  • Time complexity: O(3 * 2^n)
  • Space complexity: O(n) call stack

2. 2D Tabulation DP

Intuition

Maintain a 2D array dp[n][3] where dp[i][c] is the minimum cost to paint houses 0..i ending with color c.

Algorithm

  1. Initialize dp[n][3].
  2. dp[0] = costs[0].
  3. For i from 1 to n - 1:
  4. dp[i][0] = costs[i][0] + min(dp[i-1][1], dp[i-1][2]).
  5. dp[i][1] = costs[i][1] + min(dp[i-1][0], dp[i-1][2]).
  6. dp[i][2] = costs[i][2] + min(dp[i-1][0], dp[i-1][1]).
  7. Return min(dp[n-1][0], dp[n-1][1], dp[n-1][2]).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int minCost(vector<vector<int>>& costs) {
10 int n = costs.size();
11 if (n == 0) return 0;
12 vector<vector<int>> dp(n, vector<int>(3, 0));
13 dp[0] = costs[0];
14
15 for (int i = 1; i < n; ++i) {
16 dp[i][0] = costs[i][0] + min(dp[i - 1][1], dp[i - 1][2]);
17 dp[i][1] = costs[i][1] + min(dp[i - 1][0], dp[i - 1][2]);
18 dp[i][2] = costs[i][2] + min(dp[i - 1][0], dp[i - 1][1]);
19 }
20
21 return min({dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]});
22 }
23};
24
25int main() {
26 Solution sol;
27 vector<vector<int>> costs = {{17, 2, 17}, {16, 16, 5}, {14, 3, 19}};
28 cout << "Min Cost: " << sol.minCost(costs) << endl;
29 return 0;
30}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(n)

3. Space-Optimized 3-Variable DP (O(1) Space)

Intuition

Maintain three scalar variables representing the cumulative minimum cost ending in red, blue, and green.

Algorithm

  1. Initialize r = costs[0][0], b = costs[0][1], g = costs[0][2].
  2. For i from 1 to n - 1:
  3. newR = costs[i][0] + min(b, g).
  4. newB = costs[i][1] + min(r, g).
  5. newG = costs[i][2] + min(r, b).
  6. r = newR, b = newB, g = newG.
  7. Return min(r, b, g).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int minCost(vector<vector<int>>& costs) {
10 int n = costs.size();
11 if (n == 0) return 0;
12
13 int r = costs[0][0], b = costs[0][1], g = costs[0][2];
14
15 for (int i = 1; i < n; ++i) {
16 int newR = costs[i][0] + min(b, g);
17 int newB = costs[i][1] + min(r, g);
18 int newG = costs[i][2] + min(r, b);
19 r = newR; b = newB; g = newG;
20 }
21
22 return min({r, b, g});
23 }
24};
25
26int main() {
27 Solution sol;
28 vector<vector<int>> costs = {{17, 2, 17}, {16, 16, 5}, {14, 3, 19}};
29 cout << "Min Cost: " << sol.minCost(costs) << endl;
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(1)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive SearchO(3 * 2^n)O(n)Exhaustive branching over valid color transitions.Subproblem overlap
2.2D Tabulation DPO(n)O(n)Fill an explicit n x 3 table.Matrix allocation
3.Space-Optimized 3-Variable DPOptimalO(n)O(1)Maintain only 3 scalars for the previous house's color choices.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Updating r before using it to calculate newB and newG: Overwrites previous state prematurely (must use temporary variables or tuple unpacking).

Pitfall 2:

Greedy choice (picking the cheapest color for each house independently): Often forces an extremely expensive color on the next house.

Crucial Edge Cases to Validate:

  • n = 1: Single house; returns min(costs[0][0], costs[0][1], costs[0][2]).
  • All houses have identical costs: Alternating between the two cheaper colors is optimal.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention that this general formulation extends naturally to Paint House II with k colors in O(n * k) using tracking of the minimum and second-minimum costs.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why do we only need 3 scalar variables to solve the Paint House problem?

Back to DSA Sheet