Smallest Height Difference

MediumArraysSortingGreedy223 tests

You get an array heights with the heights of some towers, and a number k.

You must change every tower exactly once. For each tower, you either add k to its height or subtract k from it. You cannot leave a tower unchanged (unless k is 0). After the change, no height may be below 0.

Return the smallest possible difference between the tallest and the shortest tower after all the changes.

Hint

Sort the heights first. In a best answer, some short towers go up and the rest go down. Try each place where the "up" part ends and the "down" part starts, and skip a place if it would push a tower below 0.

Examples

Example 1

Input:: [1,6,9], 3
Output:: 3

1 + 3 = 4, 6 - 3 = 3, 9 - 3 = 6. The heights are 4, 3, 6. The tallest is 6 and the shortest is 3, so the difference is 3.

Example 2

Input:: [2,2,2], 4
Output:: 0

Add 4 to every tower. All heights become 6, so the difference is 0.

Example 3

Input:: [1,8,10,4], 5
Output:: 6

Towers 1 and 4 cannot go down, because 1 - 5 and 4 - 5 are below 0. They become 6 and 9. Then 8 - 5 = 3 and 10 - 5 = 5. The heights are 6, 9, 3, 5, so the difference is 9 - 3 = 6.

Constraints

1 <= heights.length <= 12
0 <= heights[i] <= 60
0 <= k <= 30

Run checks your code against the 3 examples. Submit checks it against all 223 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.