[a little intuition] Max Min

Sometimes, one must trust one's intuition. In coding problems, intuition is a really useful thing to build.

When I opened this problem, I had no idea whatsoever how to approach this problem.

Suddenly a random thought popped into my head:
What if I sorted the array, and took the first k elements?
Immediately I could think of counterexamples to disprove this notion.

1, 10, 11, 12, 13 and k  = 3

But all was not lost. We could still improve upon this. What if we looked at k length contiguous subsets of this?

1, 10, 11 | 10
10, 11, 12 | 2
11, 12, 13 | 2

And eureka! We could find the minimum difference this way.

Eureka indeed. Why does this work? If you remove all the contest pressure I had, it is plain that if the array is sorted, the difference between consecutive elements is the smallest possible, while still being non-negative. For a valid contiguous subset, we are finding the sum of the differences between consecutive elements (a bit of a mouthful there).

If the consecutive differences are minimum, then the cumulative difference between the first and last elements (min and max) is minimum, and that, solves the problem.