HackerRank October Challenge 2013 Editorial [Angry Children]

Tutorial: Sliding Window / Line Sweeping.
Problem: Angry Children
You have an array of N numbers, You have to pick K numbers where the difference of Maximum element and minimum element are minimized.

Idea: Sliding Window / Line Sweeping.
Straightforward Problem. if you are not familiar with sliding window, you can continue reading.
1st thing comes to your mind is, you should try to take elements with minimum difference to your current element. so, sort the array.
as you already sorted the array, not you can find minimum or maximum element of a segment in O(1), first element of the segment is minimum and last element of the value is maximum. thus difference of the segment can be calculate in O(1).
do a linear scan and minimize the answer. see picture below to be clear how sliding window work.
for N=8, K=3.
and the array after sorting is [1,   2,   7,   7,   17,   18,   20,   22]

here we see, in the 5th iteration we get the minimum value. (taking elements 17, 18  & 20).
so the answer is 3.

Note: this is actually a modification / simplification of original sliding window approach, in this problem you are allowed to sort the array first.

Code: 

1. #include<bits/stdc++.h>
2. using namespace std;
3.  
4. int main()
5. {
6. int arr[100001], k, n;
7. cin>>n>>k;
8. for(int i=0; i<n; i++)
9. cin>>arr[i];
10. sort(arr, arr+n);
11. int mn=1e9;
12. for(int i=0, t=i+k-1; t<n; i++, t++)
13. mn=min(mn, arr[t]-arr[i]);
14. cout<<mn<<endl;
15. return 0;
16. }

Similar Problems:
 Christmas Play
 SRM 601, div-2, 250