Author, developer, author of the analysis: Andriy Stolitniy
Consider the case where we need to collect all the oranges at coordinate .
For each orange, we need to go to it and come back. Going away from with an orange is not optimal. Thus, for each orange, we repeat the route .
The answer looks like 2 \sum_{i=1}^{n} |x_i - k|, which can be broken down into
Then we need to maintain such simple sums. We can go from the smallest to the largest, then maintaining such sums will be obvious.
Overall complexity: .