735. Paint With K Colours
A city festival decorates a row of n lamp posts. Each post is wrapped in ribbon of one of k colours, and two neighbouring posts must never get the same colour. The table costs has one row per post, and costs[i][j] is the price of dressing post i in colour j.
Return the minimum total price for the whole row. If no valid arrangement exists (this happens exactly when k is 1 and there is more than one post), return -1. A single post just takes its cheapest colour.
Aim for time O(n*k) and extra space O(k); a method that rescans all colours for every colour is too slow.
Example 1
- Input:
- costs = [[6,2,9,4],[3,8,1,7],[5,5,2,9]]
- Output:
- 7
- Explanation:
Colours 1, 0, 2 cost 2 + 3 + 2 = 7, the cheapest valid choice.
Example 2
- Input:
- costs = [[4],[6]]
- Output:
- -1
- Explanation:
With only one colour two neighbouring posts must match, so the answer is -1.
Example 3
- Input:
- costs = [[7,3],[2,9],[8,1]]
- Output:
- 6
- Explanation:
With two colours the row must alternate, and 3 + 2 + 1 = 6 beats 7 + 9 + 8.
Constraints
1 ≤ n = costs.length ≤ 2 * 104
1 ≤ k = costs[i].length ≤ 50
0 ≤ costs[i][j] ≤ 1000
The answer fits in a 32-bit signed integer.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n*k)
- Space
- O(k)