I ran into a problem while trying to solve this problem.
We’re given an array costs of integers of length N, K an integer, and we need to return the minimum sum of K non-neighbor elements of costs.

1 <= N <= 1 000 000
1 <= K <= int(N/2)
1 <= costs[i] <= 1 000 0000 0000 for all 1 <= i <= N

The intuitive approach is simple enough: run a recursive function that gradually fills a 2D cache. Not all points need to be visited, but the time complexity is still O(n*k), which is too slow.

Another approach described in this post proposes a solution in O(k* log(n)), which seems to work for me in some cases, but not in all!
An example is worth a thousand words, so first I’ll give a situation in which the algorithm as I understand it works, then one in which it doesn’t work.

N = 4
K = 2
cost = [2, 1, 2, 4]
//Expected result: 4 (2+2, any other option won't work)

We start with a sum of 0 and pair all costs[i] with their index i, then sort by cost, giving :

sum = 0
priority_queue = [[1, 1], [2, 0], [2, 2], [4, 3]]

Next, we remove the first element x from the list (here [1, 1]), add x’s cost (here 1) to the sum, remove its two neighbors from the list (2 at index 0 and 2 at index 2), then modify x’s cost so that it is the sum of the costs of the two neighbors minus x’s old cost (here 2 + 2 - 1 = 3). We then place the new x in our table, keeping it sorted.

sum = 1
priority_queue = [[3, 1], [4, 3]]

We repeat the process a total of k times: here, the smallest element x is [3, 1], so we add 3 to the sum. x has no neighbors, so we delete it completely.

sum = 4 (1+3)
priority_queue = [[3, 1], [4, 3]]

So we get the right output!

Now let’s look at an example that doesn’t work.

N = 5
K = 3
cost = [2, 1, 5, 4, 7]
//Expected result: 14 (2 + 5 + 7, the only option here)

So, as before, initially :

sum = 0
priority_queue = [[1, 1], [2, 0], [4, 3], [5, 2], [7, 4]]

Then select [1,1], add 1 to sum
Its neighbors are [2, 0] and [5, 2], remove them from the queue
Return [5+2-1, 1] = [6, 1] to the list, leaving it sorted.

sum = 1
priority_queue = [[4, 3], [6, 1], [7, 4]]

We start again with [4, 3] and its only neighbor [7, 4] (and this is where I think the mistake is).

sum = 5 (4+1)
priority_queue = [[3, 3], [6, 1]]

So on the last iteration:

sum = 8 (5 +3)
priority_queue = [[6, 1]] (no neighbors)

So we have 8 and not 14 as expected!

What’s wrong with my handling of the special case where the element has only one neighbor? Or do I just misunderstand the overall algorithm?