Paint House II

hard dp rolling array

Problem

With n houses and k colors and an n×k cost matrix, find the minimum painting cost so that no two adjacent houses share a color. Solve in O(nk).

Inputcosts = [[1,5,3],[2,9,4]]

Output5

1 then 4 = 5 (color 0 then color 2).

costs (rows by ';', cols by ',')

def min_cost_ii(costs):
    if not costs: return 0
    k = len(costs[0])
    p1 = p2 = 0
    idx1 = -1
    for row in costs:
        n1 = n2 = float("inf")
        ni1 = -1
        for c in range(k):
            cost = row[c] + (p2 if c == idx1 else p1)
            if cost < n1:
                n2 = n1; n1 = cost; ni1 = c
            elif cost < n2:
                n2 = cost
        p1, p2, idx1 = n1, n2, ni1
    return p1

function minCostII(costs) {
  if (!costs.length) return 0;
  const k = costs[0].length;
  let p1 = 0, p2 = 0, idx1 = -1;
  for (const row of costs) {
    let n1 = Infinity, n2 = Infinity, ni1 = -1;
    for (let c = 0; c < k; c++) {
      const cost = row[c] + (c === idx1 ? p2 : p1);
      if (cost < n1) { n2 = n1; n1 = cost; ni1 = c; }
      else if (cost < n2) n2 = cost;
    }
    p1 = n1; p2 = n2; idx1 = ni1;
  }
  return p1;
}

class Solution {
    public int minCostII(int[][] costs) {
        if (costs.length == 0) return 0;
        int k = costs[0].length, p1 = 0, p2 = 0, idx1 = -1;
        for (int[] row : costs) {
            int n1 = Integer.MAX_VALUE, n2 = Integer.MAX_VALUE, ni1 = -1;
            for (int c = 0; c < k; c++) {
                int cost = row[c] + (c == idx1 ? p2 : p1);
                if (cost < n1) { n2 = n1; n1 = cost; ni1 = c; }
                else if (cost < n2) n2 = cost;
            }
            p1 = n1; p2 = n2; idx1 = ni1;
        }
        return p1;
    }
}

int minCostII(vector>& costs) {
    if (costs.empty()) return 0;
    int k = costs[0].size(), p1 = 0, p2 = 0, idx1 = -1;
    for (auto& row : costs) {
        int n1 = INT_MAX, n2 = INT_MAX, ni1 = -1;
        for (int c = 0; c < k; c++) {
            int cost = row[c] + (c == idx1 ? p2 : p1);
            if (cost < n1) { n2 = n1; n1 = cost; ni1 = c; }
            else if (cost < n2) n2 = cost;
        }
        p1 = n1; p2 = n2; idx1 = ni1;
    }
    return p1;
}

Explanation

We paint n houses with k colors so no two neighbors share a color, minimizing total cost. The obvious DP would, for each house and color, scan all k previous colors to find the best different one — that is O(nk^2). The trick that makes it O(nk) is realizing you only ever need the two smallest totals from the previous row.

Why two? For a given color, the best previous choice is the previous minimum — unless that minimum was the same color, in which case we must fall back to the previous second minimum. So we carry p1 (best previous total), p2 (second-best), and idx1 (which color achieved p1).

For each house we look at every color c: its cost is row[c] plus p2 if c == idx1 (we can't reuse that color) otherwise p1. As we go we track the new smallest and second-smallest totals and the new best index.

Example: costs = [[1,5,3],[2,9,4]]. Painting house 0 color 0 (cost 1), then house 1 color 2 (cost 4) gives total 5, the minimum, since reusing color 0 is forbidden.

After the last row, p1 holds the minimum total. Tracking just two values per row keeps both time O(nk) and space O(1).

Time: O(nk) Space: O(1)