Largest and Smallest Difference

Given a list of integers nums and an integer k, choose elements from nums to create a list of length k such that the difference between the largest integer in the list and the smallest integer is minimized. Return this difference.

Constraints

• k ≤ n ≤ 100,000 where n is the length of nums

https://binarysearch.com/problems/Largest-and-Smallest-Difference

Examples

Example 1

Input

• nums = [2, 10, 5, 1, 8]
• k = 3

Output

• answer = 4

Explanation

The best list we can make is [1, 2, 5].

Solution