HackerRank MaxMin

This is solution for HackerRank MaxMin challenge, in python. This is a problem in the Interview Preparation Kit > Greedy Algorithms and is considered of medium difficulty.

Be a greedy algorithm means that the final solution will be taken by applying the same algorithm in a subset of the global problem, then comparing the local solution with previous solution on every iteration. If the current solution is better, then it will become the global solution.

Speaking of code, we usually need to:

• prepare data (once)
• run the problem in a subset
• if current solution is better, we replace global solution with current solution
• choose another subset and repeat

The problem states that:

• we receive k (number of pairs) and arr array (initial)
• there is a distracting concept of unfairness
• we need to take k elements of arr and make a new array arr'
• unfairness is max(arr') - min(arr')
• we must find the minimum unfairness

First of all, if we sort arr, we don't need to check every k subset. We can only iterate through arr find arr' because we are interested in minimum difference between min(arr') and max(arr') only. So it doesn't make sense to make arr' with values too distant to each other.

arr = [1,4,7,2]
k = 2
arr.sort() # [1,2,4,7]
for i in range(len(arr)-k+1):
   arr2 = arr[i:i+k-1]
# len(arr)-k+1 = 3 meaning i will assume 0, 1 and 2
# i=0 arr2 = [1,2]
# i=1 arr2 = [2,4]
# i=2 arr2 = [4,7]

In the example above, we should considerate only the sorted neighbors. It is unnecessary to test the arr'=[1,7] because the unfairness would by definition the bigger than [1,2] or [4,7].

We may notice that there is an iteration in arr (global problem) to find arr' (local/partial solution). Now we must find the unfairness for each sorted arr' and compare with the last one. It the current solution is better, it will replace the global solution. After iteration we will have the best solution. This is the greedy approach.

A complete python solution is shown below. The first solution (min_unfairness) is defined as the maximum unfairness of arr. Notice that arr' is defined as arr[i + k - 1] - arr[i].

def maxMin(k, arr):
    arr.sort()
    min_unfairness = arr[k] - arr[0]
    for i in range(len(arr) - k + 1):
        curr_unfairness = arr[i + k - 1] - arr[i]
        min_unfairness = min(curr_unfairness, min_unfairness)
    return min_unfairness

This function still have room for improvement. For example, it could finish if at some point curr_unfairness = 0. It could also test unfairness before replace min_unfairness. It also could add all unfairness to an array and apply min() in the return.