Given an array **arr[]** denoting heights of **n** towers and a positive integer **k**, you have to modify the height of each tower either by increasing or decreasing them by "k" only once.

After modifying, height should be a **non-negative** integer.

Find out what could be the possible minimum difference of the height of shortest and longest towers after you have modified each tower.

Input: k = 3, n = 5, arr[] = {3, 9, 12, 16, 20}

Output: 11

Input: k = 2, n = 4, arr[] = {1, 5, 8, 10}

Output: 5

## Solutions

### Method 1: Using Sorting

Follow the steps below to solve the given problem:

Sort the array.

Now current "minHeight" would be the element at the "0th" index (arr[0]), current "maxHeight" would be the element at the "n-1th" index (arr[n-1]) and current "minDiff" would be "arr[n-1]-arr[0]".

But, this is not necessarily the minimum difference possible between two towers, so we loop through the array to find the minimum difference if any.

In each iteration:

**1)** We will consider two adjacent elements, "i" and "i-1" so the loop will run from "1" to "n".

**2)** If the current element "arr[i]" is less than "k", continue, because this will turn a tower height (arr[i]-k) negative.

**3)** Find "minHeight" as "min(arr [0] + k, arr [i] - k)" and "maxHeight" as "max(arr [i - 1] + k, arr [n - 1] - k)".

**4)** Return, min (maxHeight-minHeight, minDiff).

##### Complexity

The time complexity of this solution is **O(n log n)** and space complexity is O(1).