It is a little tricky to come up with O(nk) solution, when you come up with O(nk^2) solution, you can just follow that idea, do some optimization. I think practice more can bring you more idea on those questions. When I come up with the O(nk^2) solution, my intuition tells me that I need keep track of the last two smallest elements. Then I don't need to loop all K elements to get the minimum value except for the cost for the same color. And just follow the intuition, you will finally make it.