You will be given a list of integers, $\textbf{arr}$, and a single integer $\boldsymbol{\mbox{k}}$.  You must create an array of length $\boldsymbol{\mbox{k}}$ from elements of $\textbf{arr}$ such that its unfairness is minimized. Call that array $arr'$.  Unfairness of an array is calculated as

$max(ar r')-min(arr')$  

Where: 

- max denotes the largest integer in $ar r'$ .

- min denotes the smallest integer in $ar r'$  .

Example  

$arr=[1,4,7,2]$ 

$k=2$     

Pick any two elements, say $ar r'=[4,7]$. 

$unfairness=max(4,7)-min(4,7)=7-4=3$ 

Testing for all pairs, the solution $[1,2]$ provides the minimum unfairness.

Note: Integers in $\textbf{arr}$ may not be unique. 

Function Description

Complete the maxMin function in the editor below. 

maxMin has the following parameter(s):

int k:  the number of elements to select  
int arr[n]:: an array of integers   

Returns  

int: the minimum possible unfairness  

Input Format

The first line contains an integer $n$, the number of elements in array $\textbf{arr}$. 

The second line contains an integer $\boldsymbol{\mbox{k}}$. 

Each of the next $n$ lines contains an integer $arr\left[i\right]$ where $0\leq i<n$.   

Constraints

$2\leq n\leq10^5$ 

$2\leq k\leq n$ 

$0\leq ar r[i]\leq10^9$  

Sample Input 0
7
3
10
100
300
200
1000
20
30

Sample Output 0
20

Explanation 0

Here $k=3$; selecting the $3$ integers $10,20,30$, unfairness equals  

max(10,20,30) - min(10,20,30) = 30 - 10 = 20

Sample Input 1
10
4
1
2
3
4
10
20
30
40
100
200

Sample Output 1
3

Explanation 1

Here $k=4$; selecting the $4$ integers $1,2,3,4$, unfairness equals  

max(1,2,3,4) - min(1,2,3,4) = 4 - 1 = 3

Sample Input 2
5
2
1
2
1
2
1

Sample Output 2
0

Explanation 2

Here $k=2$.  $arr'=[2,2]$ or $arr'=[1,1]$ give the minimum unfairness of $0$.

Difficulty: MEDIUM
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
import collections, sys
N = int(sys.stdin.readline())
K = int(sys.stdin.readline())
x = sorted((int(sys.stdin.readline()) for _ in range(N)))
print(min((x[i + K - 1] - x[i] for i in range(0, N - K - 1))))


import sys
N = int(sys.stdin.readline())
K = int(sys.stdin.readline())
kx = []
for n in range(N):
	kx.append(int(sys.stdin.readline()))
kx.sort()
min = 10 ** 9
for i in range(len(kx) - K + 1):
	if kx[i + K - 1] - kx[i] < min:
		min = kx[i + K - 1] - kx[i]
print(min)


def unfairness(candies, i, j):
	res = candies[j - 1] - candies[i]
	return res
n = int(input())
kids = int(input())
candies = []
for i in range(n):
	candies.append(int(input()))
candies = sorted(candies)
min_uf = unfairness(candies, 0, kids)
for i in range(1, len(candies) - kids):
	this_uf = unfairness(candies, i, i + kids)
	min_uf = min(min_uf, this_uf)
print(min_uf)


import bisect
N = int(input())
K = int(input())
arr = []
cur_max = 0
cur_min = 0
cur_unf = 0
for i in range(0, N):
	cur = int(input())
	bisect.insort(arr, cur)
can = arr[K - 1] - arr[0]
for d in range(1, N - K + 1):
	pecan = arr[d + K - 1] - arr[d]
	if pecan < can:
		can = pecan
print(can)


import sys
import sys
N = int(sys.stdin.readline())
K = int(sys.stdin.readline())
S = [0] * N
for iN in range(N):
	S[iN] = int(sys.stdin.readline())
S.sort()
minUnfairness = S[iN - 1]
for iN in range(N - K):
	minUnfairness = min(minUnfairness, S[iN + K - 1] - S[iN])
print(minUnfairness)


n = int(input())
k = int(input())
nums = []
for i in range(n):
	nums.append(int(input()))
nums.sort()
muf = nums[-1] - nums[0]
for i in range(n - k + 1):
	uf = nums[i + k - 1] - nums[i]
	if uf < muf:
		muf = uf
print(muf)


n = int(input())
k = int(input())
a = []
for i in range(n):
	a.append(int(input()))
a.sort()
ans = a[-1] - a[0]
for i in range(n - k + 1):
	ans = min(ans, a[i + k - 1] - a[i])
print(ans)


def solve(l, k):
	l = sorted(l)
	min = l[k - 1] - l[0]
	for i in range(len(l) - (k - 1)):
		if l[i + (k - 1)] - l[i] < min:
			min = l[i + (k - 1)] - l[i]
	return min

def test():
	print(solve([10, 100, 300, 200, 1000, 20, 30], 3))
	print(solve([1, 2, 3, 4, 10, 20, 30, 40, 100, 200], 4))

def main():
	N = int(input())
	k = int(input())
	l = []
	for _ in range(N):
		l.append(int(input()))
	print(solve(l, k))
main()


n = int(input())
k = int(input())
l = []
for i in range(0, n):
	x = int(input())
	l.append(x)
l.sort()
ans = 2147483647
for i in range(0, n - k):
	if ans > l[i + k - 1] - l[i]:
		ans = l[i + k - 1] - l[i]
print(ans)


def measure_unfairness(p1, p2):
	return max(p1, p2) - min(p1, p2)

def find_min(data, k):
	best = 999999999
	for i in range(len(data) - k):
		unfairness = measure_unfairness(sorted_data[i], sorted_data[i + k - 1])
		if unfairness < best:
			best = unfairness
	return best
data_slots = int(input(''))
k = int(input(''))
data = []
for i in range(data_slots):
	data.append(int(input('')))
sorted_data = sorted(data)
print(find_min(data, k))


n = int(input())
k = int(input())
l = []
for i in range(n):
	l.append(int(input()))
l.sort()
minm = l[k - 1] - l[0]
for j in range(k, n):
	minm = min(minm, l[j] - l[j - k + 1])
print(minm)


n = int(input())
k = int(input())
values = list()
for i in range(n):
	values.append(int(input()))
values.sort()
min = 9999999999999
for i in range(n - k):
	diff = values[i + k - 1] - values[i]
	if min > diff:
		min = diff
print(min)


import sys
n = int(input())
k = int(input())
lis = []
lis2 = []
for i in range(n):
	lis.append(int(input()))
lis = sorted(lis)
min = lis[k - 1] - lis[0]
for i in range(n - k):
	diff = lis[i + k - 1] - lis[i]
	if diff < min:
		min = diff
print(min)


n = int(input())
k = int(input()) - 1
a = sorted(list((int(input()) for i in range(n))))
print(min((a[i] - a[i - k] for i in range(k, n))))


N = int(input())
K = int(input())
a = []
for i in range(N):
	z = int(input())
	if z > 0:
		a.append(z)
a.sort()
sum1 = 10000000000000000
if K > 1:
	for i in range(len(a) - K + 1):
		sum1 = min(abs(a[i] - a[i + K - 1]), sum1)
	print(sum1)
else:
	print(min(a))


n = int(input())
k = int(input())
arr = []
for i in range(n):
	x = int(input())
	arr.append(x)
arr.sort()
mn = arr[k - 1] - arr[0]
for i in range(n - k):
	mn = min(arr[k + i] - arr[i + 1], mn)
print(mn)


n = int(input())
k = int(input())
a = []
for i in range(1, n + 1):
	t = int(input())
	a.append(t)
a.sort()
p = 0
q = p + k - 1
min_unfair = 100000000
while q < n:
	min_unfair = min(a[q] - a[p], min_unfair)
	p += 1
	q += 1
print(min_unfair)


n = int(input())
k = int(input())
a = []
m = 0
for i in range(n):
	a.append(int(input()))
a.sort(reverse=True)
m = a[0] - a[k - 1]
for i in range(n - k + 1):
	if a[i] - a[i + k - 1] < m:
		m = a[i] - a[i + k - 1]
print(m)


def unfairness(packets):
	return max(packets[:K]) - min(packets[:K])
import sys
N = int(sys.stdin.readline().rstrip())
K = int(sys.stdin.readline().rstrip())
packets = []
for i in range(N):
	packets.append(int(sys.stdin.readline().rstrip()))
packets.sort()
min_unfairness = packets[N - 1]
for i in range(N - K):
	if packets[i + K - 1] - packets[i] < min_unfairness:
		min_unfairness = packets[i + K - 1] - packets[i]
print(min_unfairness)


import sys
n = int(sys.stdin.readline())
k = int(sys.stdin.readline())
a = []
for _ in range(n):
	a.append(int(sys.stdin.readline()))
a.sort()
ans = a[k - 1] - a[0]
for i in range(n - k):
	ans = min(ans, a[i + k] - a[i + 1])
print(ans)


import sys
n = int(sys.stdin.readline())
k = int(sys.stdin.readline())
packs = []
for i in range(n):
	packs.append(int(sys.stdin.readline()))
packs.sort()
mindif = sum(packs)
for i in range(n - k):
	maxval = packs[i + k - 1]
	minval = packs[i]
	dif = maxval - minval
	if mindif > dif:
		mindif = dif
print(mindif)


n = int(input())
k = int(input())
candy = []
for i in range(n):
	candy.append(int(input()))
candy = sorted(candy)
minum = float('inf')
difference = []
for i in range(k - 1, n):
	difference.append(candy[i] - candy[i - k + 1])
print(min(difference))


n = int(input())
k = int(input())
a = []
for i in range(n):
	a.append(int(input()))
a.sort()
d = []
for i in range(n - k + 1):
	d.append(a[i + k - 1] - a[i])
s = min(d)
print(s)


N = int(input())
K = int(input())
Q = [int(input()) for i in range(N)]
Q.sort()
begin = 0
end = K
min = 10 ** 9
for i in range(K - 1, N):
	if min > Q[i] - Q[i - K + 1]:
		min = Q[i] - Q[i - K + 1]
print(min)


def minimumUnfairness(x, y, z):
	a = x[y - 1] - x[0]
	for i in range(z - y):
		if x[i + y - 1] - x[i] < a:
			a = x[i + y - 1] - x[i]
	print(a)
n = int(input())
m = int(input())
sweets = []
for i in range(n):
	sweets.append(int(input()))
sweets.sort()
minimumUnfairness(sweets, m, n)


N = int(input())
K = int(input())
packs = [int(input())]
for i in range(1, N):
	packs.append(int(input()))
packs.sort()
min_diff = float('inf')
for i in range(len(packs) - K + 1):
	if packs[i + K - 1] - packs[i] < min_diff:
		min_diff = packs[i + K - 1] - packs[i]
print(min_diff)


import sys
N = int(sys.stdin.readline())
K = int(sys.stdin.readline())
BAGARR = list()
for i in range(0, N):
	LINE = int(sys.stdin.readline())
	BAGARR.append(LINE)
BAGARR.sort()
MIN = 10 ** 9
for i in range(0, N - K):
	t = BAGARR[i + (K - 1)] - BAGARR[i]
	if MIN > t:
		MIN = t
print(MIN)


N = int(input())
K = int(input())
candy = []
for i in range(N):
	candy.append(int(input()))
candy.sort()
unfair = candy[K - 1] - candy[0]
for i in range(N - K + 1):
	if unfair > candy[i + K - 1] - candy[i]:
		unfair = candy[i + K - 1] - candy[i]
print(unfair)


def angry_children(n, k, candies):
	candies = sorted(candies)
	diff = candies[k - 1]
	for i in range(0, len(candies) - k):
		diff = min(diff, candies[i + k - 1] - candies[i])
	return diff

def main():
	n = int(input())
	k = int(input())
	candies = []
	for _ in range(n):
		candies.append(int(input()))
	print(angry_children(n, k, candies))
main()


N = int(input())
K = int(input())
packets = [int(input()) for i in range(N)]
packets.sort()
mini = packets[N - 1]
for i in range(N - K):
	difference = packets[i + K - 1] - packets[i]
	if difference < mini:
		mini = difference
print(mini)


from itertools import combinations
n = int(input())
k = int(input())
x = []
for _ in range(n):
	x.append(int(input()))
x.sort()
print(min((x[i + k - 1] - x[i] for i in range(0, n - k))))


n = int(input())
k = int(input())
numCan = []
for i in range(0, n):
	numCan += [int(input())]
numCan = sorted(numCan)
x = 0
y = len(numCan)
low = numCan[y - 1]
while x + k != y + 1:
	diff = numCan[x + k - 1] - numCan[x]
	x += 1
	if diff < low:
		low = diff
print(low)


n = int(input())
k = int(input())
s = []
for i in range(n):
	a = int(input())
	s.append(a)
s.sort()
d = []
for i in range(len(s) - k + 1):
	w = s[i + k - 1] - s[i]
	d.append(w)
print(min(d))


import sys

def find_min(packets, K):
	packets.sort()
	current_min = packets[K - 1] - packets[0]
	for i in range(1, len(packets) - K):
		if current_min > packets[i + K - 1] - packets[i]:
			current_min = packets[i + K - 1] - packets[i]
	return current_min
N = int(sys.stdin.readline())
K = int(sys.stdin.readline())
packets = [0] * N
for n in range(0, N):
	packets[n] = int(sys.stdin.readline())
print(find_min(packets, K))


__author__ = 'jonghewk'
packets = int(input())
children = int(input())
Ncandies = []
for i in range(packets):
	Ncandies.append(int(input()))
Ncandies.sort()
rate = float('inf')
i = 0
while i + children <= len(Ncandies):
	maxi = Ncandies[i + children - 1]
	mini = Ncandies[i]
	if maxi - mini < rate:
		rate = maxi - mini
	i += 1
print(rate)


n = int(input())
k = int(input())
a = []
for i in range(n):
	a.append(int(input()))
a = sorted(a)
minimum = a[k - 1] - a[0]
for i in range(n - k + 1):
	if a[i + k - 1] - a[i] < minimum:
		minimum = a[i + k - 1] - a[i]
print(minimum)


def readint():
	return int(input())

def go():
	n = readint()
	k = readint()
	ar = []
	for i in range(n):
		ar.append(int(input()))
	if k == 1:
		return 0
	ar = sorted(ar)
	i = 0
	j = k - 1
	ans = 10 ** 12
	while j < n:
		d = ar[j] - ar[i]
		if d < ans:
			ans = d
		i += 1
		j += 1
	return ans
print(go())


import bisect
N = int(input())
K = int(input())
cookies = []
for i in range(N):
	bisect.insort_left(cookies, int(input()))
sol = float('inf')
sol = min([cookies[i + K - 1] - cookies[i] for i in range(N - K + 1)])
print(sol)


N = int(input())
k = int(input())
numbers = []
for i in range(N):
	numbers.append(int(input()))
sortednumbers = sorted(numbers)
if N == k:
	print(sortednumbers[N - 1] - sortednumbers[0])
else:
	minimaldif = sortednumbers[N - 1] - sortednumbers[0]
	for i in range(N - (k - 1)):
		curdif = sortednumbers[i + (k - 1)] - sortednumbers[i]
		if curdif < minimaldif:
			minimaldif = curdif
	print(minimaldif)


Candies = []
(n, k) = (int(input()), int(input()))
unfairness = 10000000000
for _ in range(n):
	Candies.append(int(input()))
Candies.sort()
for i in range(0, n - k + 1):
	unfairness = min(unfairness, Candies[i + k - 1] - Candies[i])
print(unfairness)


N = int(input())
K = int(input())
candy_array = []
i = 0
diff = 1000000000000000000000000
while i < N:
	candy_array.append(int(input()))
	i += 1
candy_array.sort()
i = 0
while i < N - K:
	temp = candy_array[i + (K - 1)] - candy_array[i]
	if temp < diff:
		diff = temp
	i += 1
print(diff)


import sys
N = int(sys.stdin.readline())
K = int(sys.stdin.readline())
x = sorted((int(sys.stdin.readline()) for _ in range(N)))
print(min((x[i + K - 1] - x[i] for i in range(0, N - K - 1))))


n = int(input())
k = int(input())
args = []
for numtest in range(n):
	args.append(int(input()))
args = sorted(args)
unfairness = []
for i in range(n - k):
	unfairness.append(args[i + k - 1] - args[i])
print(min(unfairness))


n = int(input())
k = int(input())
a = []
for i in range(n):
	a.append(int(input()))
a.sort()
d = []
for i in range(n - k + 1):
	d.append(a[i + k - 1] - a[i])
s = min(d)
print(s)


N = int(input())
K = int(input())
packets = []
for i in range(N):
	packets.append(int(input()))
packets.sort()
i = 0
j = K - 1
unfairness = packets[-1] - packets[0]
while j < N:
	unfairness = min(packets[j] - packets[i], unfairness)
	i += 1
	j += 1
print(unfairness)


n = int(input())
k = int(input())
a = []
for i in range(n):
	a.append(int(input()))
a.sort()
dif = abs(a[0] - a[k - 1])
for i in range(1, n - k):
	if abs(a[i] - a[i + k - 1]) < dif:
		dif = abs(a[i] - a[i + k - 1])
print(dif)


n = int(input())
k = int(input())
candies = sorted([int(input()) for i in range(n)])
unfairnesses = sorted([candies[i + k - 1] - candies[i] for i in range(n - k)])
print(unfairnesses[0])


n = int(input())
k = int(input())
vals = []
for i in range(n):
	vals.append(int(input()))
vals.sort()
minDiff = vals[-1]
for i in range(n - k + 1):
	diff = vals[i + k - 1] - vals[i]
	if diff < minDiff:
		minDiff = diff
print(minDiff)


def main():
	N = int(input())
	K = int(input())
	packets = []
	for i in range(N):
		packets.append(int(input()))
	packets = sorted(packets)
	mindiff = packets[-1]
	for i in range(len(packets) - K + 1):
		diff = packets[i + K - 1] - packets[i]
		mindiff = min(mindiff, diff)
	print(mindiff)
	return 0
main()


n = int(input())
k = int(input())
vec = []
for i in range(0, n):
	vec.append(int(input()))
vec.sort()
m = vec[-1] - vec[len(vec) - k + 1]
for i in range(0, n - k + 1):
	if vec[i + k - 1] - vec[i] < m:
		m = vec[i + k - 1] - vec[i]
print(m)


N = int(input())
K = int(input())
data = []
for _ in range(N):
	data.append(int(input()))
max_unfairness = float('inf')
data.sort()
for i in range(N - K):
	unfairness = data[i + K - 1] - data[i]
	if unfairness < max_unfairness:
		max_unfairness = unfairness
print(max_unfairness)


import sys

def min_unfairness(nums):
	N = nums[0]
	K = nums[1]
	packets = sorted(nums[2:])
	result = packets[N - 1] - packets[0]
	for i in range(0, N - K + 1):
		result = min(result, packets[i + K - 1] - packets[i])
	return result
print(min_unfairness([int(line) for line in sys.stdin]))


N = int(input())
K = int(input())
X = [int(input()) for _ in range(0, N)]
X.sort()
m = X[K - 1] - X[0]
for n in range(1, N - K):
	if X[K - 1 + n] - X[n] < m:
		m = X[K - 1 + n] - X[n]
print(m)


N = int(input())
K = int(input())
dat = []
for i in range(0, N):
	dat.append(int(input()))
dat.sort()
best = max(dat)
for i in range(0, N - K):
	if dat[i + K - 1] - dat[i] < best:
		best = dat[i + K - 1] - dat[i]
print(best)


n = int(input())
k = int(input())
candies = []
for i in range(n):
	candies.append(int(input()))
candies.sort()
u = []
for i in range(n - k):
	u.append(candies[i + k - 1] - candies[i])
print(min(u))


import sys
n = int(sys.stdin.readline())
k = int(sys.stdin.readline())
arr = []
for i in range(0, n):
	arr.append(int(sys.stdin.readline()))
arr.sort()
start = 0
min = 10000000000
while start + k < len(arr):
	asum = arr[start + k - 1] - arr[start]
	if asum < min:
		min = asum
	start += 1
print(min)


import sys
from itertools import islice
n = int(input())
k = int(input()) - 1
lis = islice(sys.stdin, n)
ar = [int(i) for i in lis]
ar.sort()
d = ar[n - 1]
for i in range(n - k):
	d1 = ar[i + k] - ar[i]
	if d1 < d:
		d = d1
print(d)


N = int(input())
K = int(input())
cp = []
for i in range(N):
	cp.append(int(input()))
cp.sort()
min = cp[-1] - cp[0]
for i in range(len(cp) - (K - 1)):
	temp = cp[i + (K - 1)] - cp[i]
	if min > temp:
		min = temp
print(min)


packets = int(input())
children = int(input())
candy = []
for i in range(packets):
	candy.append(int(input()))
candy.sort()
counter = []
for a in range(packets - children + 1):
	b = a + children - 1
	v = candy[b] - candy[a]
	counter.append(v)
print(min(counter))


n = int(input())
k = int(input())
l = []
for i in range(0, n):
	x = int(input())
	l.append(x)
l.sort()
result = -1
for i in range(0, n - k):
	if -1 == result or result > l[i + k - 1] - l[i]:
		result = l[i + k - 1] - l[i]
print(result)


N = int(input())
K = int(input())
candies = []
for _ in range(N):
	candies.append(int(input()))
candies.sort()
unfairness = candies[K - 1] - candies[0]
for i in range(0, N - K):
	unfairness = min(unfairness, candies[i + K - 1] - candies[i])
print(unfairness)


n = int(input())
k = int(input())
candies = []
for i in range(n):
	candies.append(int(input()))
candies.sort()
ret = 1000000005
for i in range(n - k + 1):
	ret = min(ret, candies[i + k - 1] - candies[i])
print(ret)


N = int(input())
K = int(input())
ALL = []
for i in range(N):
	ALL.append(int(input()))
ALL.sort()
minimum = 10 ** 10
for index in range(N - K):
	m = ALL[index + K - 1] - ALL[index]
	if m < minimum:
		minimum = m
print(minimum)


n = int(input())
k = int(input())
l = []
for i in range(n):
	l.append(int(input()))
l.sort()
diff = l[-1]
for i in range(n - k + 1):
	if l[i + k - 1] - l[i] < diff:
		diff = l[i + k - 1] - l[i]
print(diff)


N = int(input())
K = int(input())
i = 0
listOfCandies = []
while i < N:
	listOfCandies.append(int(input()))
	i += 1
listOfCandies.sort()
betterDif = 10 ** 9
i = 0
while i < len(listOfCandies) - K:
	diff = listOfCandies[K + i - 1] - listOfCandies[i]
	if diff < betterDif:
		betterDif = diff
	i += 1
print(betterDif)


def g(n):
	l = []
	while n > 0:
		x = int(input())
		l.append(x)
		n = n - 1
	return l

def f(n, k, l):
	l.sort()
	z = []
	for i in range(n - k):
		z.append(l[i + k - 1] - l[i])
	return min(z)
n = int(input())
k = int(input())
print(f(n, k, g(n)))


def f(t, k):
	ans = []
	for i in range(1, t + 1):
		ni = int(input())
		ans.append(ni)
	return g(ans, k)

def g(l, k):
	l.sort()
	anss = []
	n = len(l)
	for i in range(0, n - k + 1):
		anss.append(l[i + k - 1] - l[i])
	return min(anss)
t = int(input())
k = int(input())
print(f(t, k))


import sys

def minimum_unfairness(packets, children):
	packets.sort()
	min_unfairness = sys.maxsize
	for i in range(len(packets)):
		if i + children < len(packets):
			current_unfairness = packets[i + children - 1] - packets[i]
			if current_unfairness < min_unfairness:
				min_unfairness = current_unfairness
	return min_unfairness
num_packets = int(input())
num_children = int(input())
packets = [int(input()) for _ in range(num_packets)]
print(minimum_unfairness(packets, num_children))


n = int(input())
k = int(input())
gr = []
dat = []
for c in range(n):
	gr.append(int(input()))
gr.sort()
for z in range(n - k):
	dat.append(gr[z + k - 1] - gr[z])
print(min(dat))


nL = int(input())
k = int(input())
n = [int(input()) for _ in range(nL)]
n.sort()
best = n[k - 1] - n[0]
for i in range(nL - k + 1):
	if n[i + k - 1] - n[i] < best:
		best = n[i + k - 1] - n[i]
print(best)


import sys

def solve(L, k):
	_min = sys.maxsize
	L = sorted(L)
	for i in range(k - 1, len(L)):
		_min = min(_min, L[i] - L[i + 1 - k])
	return _min
n = int(input())
k = int(input())
L = []
for i in range(n):
	L.append(int(input()))
print(solve(L, k))


import sys
line_no = 1
packs = []
num_packs = int(sys.stdin.readline())
num_choices = int(sys.stdin.readline())
for line in sys.stdin.readlines():
	packs.append(int(line))
packs = sorted(packs)
optimal = float('inf')
for pack_index in range(num_packs):
	start = pack_index
	end = pack_index + num_choices - 1
	try:
		candidate_unfairness = packs[end] - packs[start]
		optimal = min(optimal, candidate_unfairness)
	except IndexError:
		break
print(optimal)


import sys

def calculateMinimumUnfairness(numPackets, packets, children):
	packets.sort()
	currentMinimum = -1
	endOfRange = 1 + numPackets - children
	for i in range(0, endOfRange):
		endOfSample = i + children - 1
		unfairness = packets[endOfSample] - packets[i]
		if currentMinimum == -1 or currentMinimum > unfairness:
			currentMinimum = unfairness
	return currentMinimum
numPackets = int(sys.stdin.readline())
numChildren = int(sys.stdin.readline())
packets = list()
for i in range(0, numPackets):
	packets.append(int(sys.stdin.readline()))
print(calculateMinimumUnfairness(numPackets, packets, numChildren))


import bisect
n = int(input())
k = int(input())
mins = []
maxs = []
m = n - k + 1
for i in range(n):
	c = int(input())
	if len(mins) < m:
		bisect.insort_left(mins, c)
	elif c < mins[-1]:
		del mins[-1]
		bisect.insort_left(mins, c)
	if len(maxs) < m:
		bisect.insort_left(maxs, c)
	elif c > maxs[0]:
		del maxs[0]
		bisect.insort_left(maxs, c)
res = [maxs[i] - mins[i] for i in range(len(maxs) - 1)]
print(min(res))


n = int(input())
k = int(input())
c = 0
lis = []
dif = []
while n > c:
	lis.append(int(input()))
	c = c + 1
lis.sort()
for i in range(len(lis) - k + 1):
	dif.append(lis[i + k - 1] - lis[i])
dif.sort()
print(dif[0])


num = int(input())
kids = int(input())
packets = []
answer = set()
for _ in range(num):
	packets.append(int(input()))
packets = sorted(packets)
for i in range(num - kids):
	answer.add(packets[kids + i - 1] - packets[i])
print(min(answer))


def doMath(s, k):
	s.sort()
	minDist = 99999999
	for i in range(len(s) - k):
		if s[i + k - 1] - s[i] < minDist:
			minDist = s[i + k - 1] - s[i]
	return minDist
n = int(input())
k = int(input())
s = []
for i in range(n):
	s.append(int(input()))
print(doMath(s, k))


n = int(input())
k = int(input())
packets = [int(input()) for _ in range(n)]
packets.sort()
print(min([packets[x + k - 1] - packets[x] for x in range(n - k - 1)]))


N = int(input())
K = int(input())
assert 1 <= N <= 10 ** 5
assert 1 <= K <= N
lis = []
for i in range(N):
	lis.append(int(input()))
lis.sort()
for i in lis:
	assert 0 <= i <= 10 ** 9
answer = 100000000000000000000
for index in range(N - K + 1):
	diff = lis[index + K - 1] - lis[index]
	if diff < answer:
		answer = diff
print(answer)


def angry_children(k, packets):
	packets.sort()
	n = len(packets)
	best_unfairness = float('inf')
	for i in range(n - k + 1):
		unfairness = packets[i + k - 1] - packets[i]
		if unfairness < best_unfairness:
			best_unfairness = unfairness
	print(best_unfairness)
N = int(input())
K = int(input())
packets = []
for _ in range(N):
	packets.append(int(input()))
angry_children(K, packets)


N = int(input())
K = int(input())
candy = []
for x in range(N):
	candy.append(int(input()))
candy.sort()
small = 10 ** 9
for x in range(N - K + 1):
	try:
		if candy[x + K - 1] - candy[x] < small:
			small = candy[x + K - 1] - candy[x]
	except:
		pass
print(small)


N = int(input())
K = int(input())
packets = list((int(input()) for _ in range(N)))
packets.sort(reverse=True)
unfairness = float('inf')
for i in range(0, len(packets) - K + 1):
	current_unfair = packets[i] - packets[i + K - 1]
	if current_unfair < unfairness:
		unfairness = current_unfair
print(unfairness)


__author__ = 'Murugan'
N = int(input())
K = int(input())
lst = []
for i in range(N):
	lst.append(int(input()))
lst.sort()
fairness = lst[-1]
for i in range(N - K):
	diff = lst[i + (K - 1)] - lst[i]
	if fairness > diff:
		fairness = diff
print(fairness)


import sys

def unfairness(lo, hi):
	return hi - lo
lines = list(sys.stdin)
k = int(lines[1])
amounts = list(sorted([int(i) for i in lines[2:]]))
print(min([unfairness(amounts[i], amounts[i + k - 1]) for i in range(len(amounts) - k)]))


N = int(input())
K = int(input())
n = sorted([int(input()) for i in range(N)])
minf = -1
for i in range(N - K + 1):
	fairness = n[i + K - 1] - n[i]
	if fairness < minf or minf == -1:
		minf = fairness
print(minf)


import sys
numberOfPackets = int(sys.stdin.readline())
numberOfPicks = int(sys.stdin.readline())
packets = []
for index in range(numberOfPackets):
	packets.append(int(sys.stdin.readline()))
packets.sort()
minimalUnfairness = 9999999999
for index in range(numberOfPackets - numberOfPicks + 1):
	sum = 0
	unfairness = packets[index + numberOfPicks - 1] - packets[index]
	if unfairness < minimalUnfairness:
		minimalUnfairness = unfairness
print(minimalUnfairness)


n = int(input())
k = int(input())
xs = []
for i in range(n):
	xs.append(int(input()))
xs.sort()
print(min((xs[i] - xs[i - k + 1] for i in range(k - 1, n))))


def fun():
	n = input()
	n1 = int(n)
	k = input()
	k1 = int(k)
	li = []
	for i in range(n1):
		ip = input()
		li.append(int(ip))
	li.sort()
	ans = 1000000000
	for i in range(n1 - k1 + 1):
		diff = li[i + k1 - 1] - li[i]
		if diff < ans:
			ans = diff
	print(ans)
fun()


import sys, itertools
sys.stdin.readline()
k = int(sys.stdin.readline())
candies = []
for l in sys.stdin:
	candies.append(int(l))
candies = sorted(candies)
min_dif = None
for i in range(len(candies) - k):
	dif = candies[i + k - 1] - candies[i]
	if min_dif is not None:
		if dif < min_dif:
			min_dif = dif
	else:
		min_dif = dif
print(min_dif)


import sys
numitems = int(sys.stdin.readline())
numselections = int(sys.stdin.readline())
tests = []
for i in range(numitems):
	tests.append(int(sys.stdin.readline()))
tests.sort()
diff = tests[numitems - 1]
for i in range(numitems - numselections):
	if diff > tests[i + numselections - 1] - tests[i]:
		diff = tests[i + numselections - 1] - tests[i]
print(diff)


import sys
N = int(sys.stdin.readline())
K = int(sys.stdin.readline())
x = sorted((int(sys.stdin.readline()) for _ in range(N)))
print(min((x[i + K - 1] - x[i] for i in range(0, N - K - 1))))


N = int(input())
K = int(input())
candies = sorted([int(input()) for i in range(N)])
min_unfairness = candies[-1]
for i in range(N - K):
	min_unfairness = min(min_unfairness, candies[i + K - 1] - candies[i])
print(min_unfairness)


n = int(input())
k = int(input())
arr = []
for _ in range(n):
	arr.append(int(input()))
arr.sort()
print(min((arr[i + k - 1] - arr[i] for i in range(n - k + 1))))


import sys
N = int(sys.stdin.readline())
K = int(sys.stdin.readline())
xs = sorted([int(X) for X in sys.stdin.readlines()])
diffs = [xs[i + K - 1] - xs[i] for i in range(N - K + 1)]
print(min(diffs))


import sys
n = int(sys.stdin.readline())
k = int(sys.stdin.readline())
n_list = []
for i in range(n):
	n_list.append(int(sys.stdin.readline()))
n_list.sort()
minim = n_list[-1]
for i in range(n - k):
	s = n_list[i + k - 1] - n_list[i]
	if s < minim:
		minim = s
sys.stdout.write(str(minim))


import sys
f = sys.stdin
num_bags = int(f.readline())
num_kids = int(f.readline())
i = 0
vals = []
while i < num_bags:
	vals.append(int(f.readline()))
	i += 1
vals.sort()
dif = []
for i in range(0, len(vals) - num_kids):
	dif.append((i, i + num_kids, vals[i + num_kids - 1] - vals[i]))
dif = sorted(dif, key=lambda x: x[2])
print(dif[0][2])