Quick Overview

This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Minimize adjacent-color assignment cost states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Minimize adjacent-color assignment cost

Company: LinkedIn

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given H linear items (e.g., houses) and an H×C cost matrix where cost[i][c] is the cost of assigning color c to item i. Adjacent items cannot share the same color. Design algorithms to compute the minimum total cost: (a) a top-down recursive solution with memoization and (b) a bottom-up dynamic program with space optimization. Return the minimum cost and also reconstruct one optimal assignment. Analyze time and space for C=3 and for general C, discuss how to reduce space to O (C), and cover edge cases (H=0, C=0/1, large costs).

Quick Answer: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Minimize adjacent-color assignment cost states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

You are given H linear items (e.g. houses) in a row and an H×C cost matrix `cost`, where `cost[i][c]` is the cost of painting item i with color c. No two ADJACENT items may share the same color. Return the minimum total cost to paint every item. This generalizes LeetCode 'Paint House' (C=3) to any number of colors C. The intended solution is dynamic programming: let dp[i][c] be the minimum cost to paint items 0..i with item i colored c. Then dp[i][c] = cost[i][c] + min over c'≠c of dp[i-1][c']. A naive transition is O(H·C²); by tracking the smallest and second-smallest values of the previous row you reduce the transition to O(C), giving O(H·C) time and O(C) space (one rolling row). The same recurrence can also be written top-down with memoization. Edge cases: H=0 (empty matrix) → cost 0; C=1 with H=1 → that single cell's cost (with H>1 and C=1 there is no valid coloring — by convention this implementation returns -1, but valid inputs have C≥2 whenever H≥2). Implement `minCost(cost)` returning the minimum total cost as an integer.

Constraints

  • 0 <= H <= 10^5 (number of items / rows)
  • 1 <= C <= 100 (number of colors / columns) when H >= 1
  • 0 <= cost[i][c] <= 10^6
  • Every row of `cost` has exactly C entries
  • Adjacent items (i and i+1) must receive different colors
  • If H == 0 the answer is 0 (nothing to paint)

Examples

Input: ([[17, 2, 17], [16, 16, 5], [14, 3, 19]],)

Expected Output: 10

Explanation: Pick color1 (2) for item0, color2 (5) for item1, color1 (3) for item2 — no two adjacent share a color: 2 + 5 + 3 = 10, the minimum.

Input: ([[7, 6, 2]],)

Expected Output: 2

Explanation: Single item with no adjacency constraint — just take the cheapest color (2).

Hints

  1. Define dp[i][c] = minimum cost to paint items 0..i with item i colored c. The transition only depends on the previous row, so you can keep just one rolling row → O(C) space.
  2. dp[i][c] = cost[i][c] + min(dp[i-1][c'] for c' != c). Computing that min naively for every c is O(C²) per row.
  3. Speed the transition to O(C): from the previous row, precompute the smallest value m1 (at color index i1) and the second-smallest value m2. For color c, the best predecessor is m1 unless c == i1, in which case it is m2.
  4. Handle edges first: empty matrix → 0; a single row → min of that row; C == 1 only colorable when H <= 1.

Loading coding console...