Tuesday, February 10, 2015

Finding a sub list with least max-min difference - Codeforces puzzle

This is a problem from Codeforces. Please follow this link to solve this problem on your own.

The abridged problem statement is as follows.

You are given an list of numbers, and sub-list size as input. The challenge is to find a sub-list such that the difference between the maximum and minimum numbers in that sub-list is minimized.

For example consider the numbers {36, 6, 12, 42, 24, 50}, and we have to find a sub-list of size 4. By choosing {36, 42, 24, 50}, we can have a least difference of 26 i.e 50-24.

The solution is to first sort the numbers in ascending order, and move a sliding window of sub-list size from begin to end while keeping track of the minimum difference between first and last numbers of the sub-list.

Tracing with the above example, after sorting the list becomes {6, 12, 24, 36, 42, 50}
We start with 6, 36, the difference is 30
move on to 12, 42, the difference is 30
move on to 24, 50, the difference is 26
So the minimum difference is 26.

This algorithm runs in O(n*log n) time because we have to sort the list. the actual algorithm takes O(n), linear time.

Here is the C++ code for the same.