How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at LinkedIn.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at LinkedIn during technical interviews.

Minimize adjacent-color assignment cost | LinkedIn Coding Question

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).

Input: ([],)

Expected Output: 0

Explanation: Empty matrix (H = 0): nothing to paint, so the minimum cost is 0.

Input: ([[1, 5, 3], [2, 9, 4]],)

Expected Output: 5

Explanation: Color item0 with 1 then item1 must avoid that color: cheapest remaining is 4 → 5. (Coloring item0 with 3 then item1 with 2 also gives 5.)

Input: ([[5]],)

Expected Output: 5

Explanation: Single 1x1 cell (C = 1, H = 1): the only choice costs 5.

Input: ([[1, 100], [100, 1], [1, 100], [100, 1]],)

Expected Output: 4

Explanation: Alternate the two cheap diagonal cells (1 each): 1 + 1 + 1 + 1 = 4; any same-adjacent choice would force an expensive 100.

Input: ([[3, 5, 3], [6, 17, 6], [7, 13, 18], [9, 10, 18]],)

Expected Output: 26

Explanation: Optimal path through the DP keeping adjacent colors distinct totals 26 (verified by the reference DP).

Hints

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.
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.
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.
Handle edges first: empty matrix → 0; a single row → min of that row; C == 1 only colorable when H <= 1.

Quick Overview