Process either the smaller or the largest element, depending which is closer (in value, not index) to the starting element, then simply process the remaining elements to the right or to the left (depending on whether we processed the smallest or the largest element).
So, given 4,9,10,11,19
starting from 10
:
The distance from 10
to the smallest element 4
is 6, the distance from 10
to the largest element 19
is 9, so move to 4
.
Then process the remaining elements in sorted order - 9, 11, 19
.
This gives us 10 -> 4 -> 9 -> 11 -> 19
, which costs 6 + 5 + 2 + 8 = 21
.
This can be done in O(n)
.
Note:
It's worth noting that as long as we first move towards the closest side, then towards the other side (regardless of which elements we process when, as long as we don't change direction more than once), we'll get an optimal result.
That's why 10 -> 9 -> 4 -> 11 -> 19
also gives 21
.