Practice/LinkedIn/Leetcode 265. Paint House II

Leetcode 265. Paint House II

CodingMust

Problem

You are planning to paint a row of houses in a neighborhood. Each house must be painted with exactly one color from a palette of available colors. The painting company has provided you with a cost matrix where each entry represents the cost of painting a specific house with a specific color.

There is one important aesthetic constraint: no two adjacent houses can be painted with the same color. Your goal is to determine the minimum total cost to paint all houses while respecting this constraint.

You are given a 2D array costs where costs[i][j] represents the cost of painting house i with color j.

Requirements

1. Every house must be painted with exactly one color
2. No two adjacent houses can have the same color
3. Return the minimum total cost to paint all houses
4. The solution must handle large numbers of color options efficiently

Constraints

• 1 ≤ number of houses ≤ 100
• 1 ≤ number of colors ≤ 20
• 1 ≤ costs[i][j] ≤ 20
• Your algorithm should aim for O(n × k) time complexity where n is the number of houses and k is the number of colors

Examples

Example 1:

Input: costs = [[1,5,3],[2,9,4]] Output: 5 Explanation: Paint house 0 with color 0 (cost 1) and house 1 with color 2 (cost 4). Total cost = 1 + 4 = 5

Example 2:

Input: costs = [[7,3,8,6,1,9]] Output: 1 Explanation: Only one house exists, so choose the cheapest color which costs 1.

Example 3:

` Input: costs = [[1,3,5,7],[4,2,8,3],[6,1,2,5]] Output: 5 Explanation: One optimal solution is:

• House 0: color 0 (cost 1)
• House 1: color 1 (cost 2)
• House 2: color 2 (cost 2) Total cost = 1 + 2 + 2 = 5 `