# HALLOWEEN EVE - APOC2_02 - EDITORIAL

## PROBLEM LINK

*Author*: codechefsrm

*Editorialist* : codechefsrm

## DIFFICULTY

MEDIUM-HARD

## PREREQUISITES

Vector,Sorting,Arrays and Subsets

## PROBLEM

In some other world, today is Halloween Eve.There are N trees planted in Mr. Smithís garden. The height of the i-th tree (1=i=N) is h i meters.

He decides to choose K trees from these trees and decorate them with electric lights. To make the scenery more beautiful, the heights of the

decorated trees should be as close to each other as possible.More specifically, let the height of the tallest decorated tree be hmax meters,

and the height of the shortest decorated tree be hmin meters.The smaller the value hmax-hmin is, the better. What is the minimum possible value

of hmax-hmin?

Constraints 2<=K<N<=105

1<=hi<=109

h i is an integer.

Input

Input is given from Standard Input in the following format: N K

h1 h2

:

hN

Output

Print the minimum possible value of hmax-hmin.

## EXPLANATION

Get the input in the given format. Find the difference between minimum and maximum of all possible K-subsets.Store the minimum of the difference

in a variable.Output the minimum stored in the variable.

Example Test Case:

Input:

5 3

10

15

11

14

12

Output:

2

In the above example,

Find the difference of maximum and minimum in a subset of 3.

Subset 1:{10,15,11}

Diff=15-10=5

Subset 2:{15,11,14}

diff=15-11=4

Subset 3:{11,14,12}

diff=14-11=3

.

.

.

.

Subset n:{10,11,12}

diff=12-10=2

Hence the minimum difference is 2.

## Program

## Setter's Solution

#include<bits/stdc++.h>

using namespace std;

using pp=pair<int,int>;

int main(){

int N,K;

cin>>N >>K;

vectorh(N);

for(int i=0;i<N;i++){

cin>>h[i];

}

sort(h.begin(),h.end());

int H=1000000000;

for(int i=0;i<N-K+1;i++){

H=min(H,h[i+K-1]-h[i]);

}

cout<<H<<endl;

}