[Greedy] HackerRank Algorithms in Java ‘Max Min’ solution

Problem

You will be given a list of integers, arr, and a single integer k. You must create an array of length k from elements of arr such that its unfairness is minimized. Call that array subarr. Unfairness of an array is calculated as max(subarr) - min(subarr)
Where:

• max denotes the largest integer in subarr
• min denotes the smallest integer in subarr

As an example, consider the array [1,4,7,2] with a k of 2. Pick any two elements, test subarr = [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 arr may not be unique.

Sample Input 0

7
3
10
100
300
200
1000
20
30

Sample Output 0

20

Solution

입력 받은 배열을 오름차순으로 정렬 후 k개의 숫자를 뽑아 k번째 수(max)와 첫번째 수 (min)의 차이가 가장 작은 것을 출력한다.

Code

    // Complete the maxMin function below.
    static int maxMin(int k, int[] arr) {
        Arrays.sort(arr);
        
        int min = Integer.MAX_VALUE;
        for(int i = 0; i <= arr.length - k; i++) 
            min = Math.min(min, arr[k + i - 1] - arr[i]);
        return min;
    }