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.

## Top comments (0)