# Choose k array elements such that difference of maximum and minimum is minimized

Given an array of **n** integers and a positive number **k**. We are allowed to take any k integers from the given array. The task is to find the minimum possible value of the difference between maximum and minimum of K numbers.

**Examples:**

Input : arr[] = {10, 100, 300, 200, 1000, 20, 30} k = 3 Output : 20 20 is the minimum possible difference between any maximum and minimum of any k numbers. Given k = 3, we get the result 20 by selecting integers {10, 20, 30}. max(10, 20, 30) - min(10, 20, 30) = 30 - 10 = 20. Input : arr[] = {1, 2, 3, 4, 10, 20, 30, 40, 100, 200}. k = 4 Output : 3

The idea is to sort the array and choose k continuous integers. Why continuous? Let the chosen k integers be arr[0], arr[1], â€¦arr[r], arr[r+x]…, arr[k-1], all in increasing order but not continuous in the sorted array. This means there exists an integer p which lies between arr[r] and arr[r+x],. So if p is included and arr[0] is removed, then the new difference will be arr[r] – arr[1] whereas old difference was arr[r] – arr[0]. And we know arr[0] â‰¤ arr[1] â‰¤ â€¦ â‰¤ arr[k-1] so minimum difference reduces or remains the same. If we perform the same procedure for other p like numbers, we get the minimum difference.

Algorithm to solve the problem:

- Sort the Array.
- Calculate the maximum(k numbers) – minimum(k numbers) for each group of k consecutive integers.
- Return minimum of all values obtained in step 2.

Below is the implementation of above idea :

## C++

`// C++ program to find minimum difference of maximum` `// and minimum of K number.` `#include<bits/stdc++.h>` `using` `namespace` `std;` `// Return minimum difference of maximum and minimum` `// of k elements of arr[0..n-1].` `int` `minDiff(` `int` `arr[], ` `int` `n, ` `int` `k)` `{` ` ` `int` `result = INT_MAX;` ` ` `// Sorting the array.` ` ` `sort(arr, arr + n);` ` ` `// Find minimum value among all K size subarray.` ` ` `for` `(` `int` `i=0; i<=n-k; i++)` ` ` `result = min(result, arr[i+k-1] - arr[i]);` ` ` `return` `result;` `}` `// Driven Program` `int` `main()` `{` ` ` `int` `arr[] = {10, 100, 300, 200, 1000, 20, 30};` ` ` `int` `n = ` `sizeof` `(arr)/` `sizeof` `(arr[0]);` ` ` `int` `k = 3;` ` ` `cout << minDiff(arr, n, k) << endl;` ` ` `return` `0;` `}` |

## Java

`// Java program to find minimum difference` `// of maximum and minimum of K number.` `import` `java.util.*;` `class` `GFG {` ` ` `// Return minimum difference of` `// maximum and minimum of k` `// elements of arr[0..n-1].` `static` `int` `minDiff(` `int` `arr[], ` `int` `n, ` `int` `k) {` ` ` `int` `result = Integer.MAX_VALUE;` ` ` `// Sorting the array.` ` ` `Arrays.sort(arr);` ` ` `// Find minimum value among` ` ` `// all K size subarray.` ` ` `for` `(` `int` `i = ` `0` `; i <= n - k; i++)` ` ` `result = Math.min(result, arr[i + k - ` `1` `] - arr[i]);` ` ` `return` `result;` `}` `// Driver code` `public` `static` `void` `main(String[] args) {` ` ` `int` `arr[] = {` `10` `, ` `100` `, ` `300` `, ` `200` `, ` `1000` `, ` `20` `, ` `30` `};` ` ` `int` `n = arr.length;` ` ` `int` `k = ` `3` `;` ` ` `System.out.println(minDiff(arr, n, k));` `}` `}` `// This code is contributed by Anant Agarwal.` |

## Python3

`# Python program to find minimum` `# difference of maximum` `# and minimum of K number.` `# Return minimum difference` `# of maximum and minimum` `# of k elements of arr[0..n-1].` `def` `minDiff(arr,n,k):` ` ` `result ` `=` `+` `2147483647` ` ` ` ` `# Sorting the array.` ` ` `arr.sort()` ` ` ` ` `# Find minimum value among` ` ` `# all K size subarray.` ` ` `for` `i ` `in` `range` `(n` `-` `k` `+` `1` `):` ` ` `result ` `=` `int` `(` `min` `(result, arr[i` `+` `k` `-` `1` `] ` `-` `arr[i]))` ` ` ` ` `return` `result` `# Driver code` `arr` `=` `[` `10` `, ` `100` `, ` `300` `, ` `200` `, ` `1000` `, ` `20` `, ` `30` `]` `n ` `=` `len` `(arr)` `k ` `=` `3` ` ` `print` `(minDiff(arr, n, k))` `# This code is contributed` `# by Anant Agarwal.` |

## C#

`// C# program to find minimum` `// difference of maximum and` `// minimum of K number.` `using` `System;` `class` `GFG {` ` ` `// Return minimum difference of` `// maximum and minimum of k` `// elements of arr[0..n - 1].` `static` `int` `minDiff(` `int` `[]arr, ` `int` `n,` ` ` `int` `k)` `{` ` ` `int` `result = ` `int` `.MaxValue;` ` ` `// Sorting the array.` ` ` `Array.Sort(arr);` ` ` `// Find minimum value among` ` ` `// all K size subarray.` ` ` `for` `(` `int` `i = 0; i <= n - k; i++)` ` ` `result = Math.Min(result, arr[i + k - 1] - arr[i]);` ` ` `return` `result;` `}` `// Driver code` `public` `static` `void` `Main() {` ` ` `int` `[]arr = {10, 100, 300, 200, 1000, 20, 30};` ` ` `int` `n = arr.Length;` ` ` `int` `k = 3;` ` ` `Console.WriteLine(minDiff(arr, n, k));` `}` `}` `// This code is contributed by vt_m.` |

## PHP

`<?php` `// PHP program to find minimum` `// difference of maximum and` `// minimum of K number.` `// Return minimum difference` `// of maximum and minimum` `// of k elements of arr[0..n-1].` `function` `minDiff(` `$arr` `, ` `$n` `, ` `$k` `)` `{` ` ` `$INT_MAX` `= 2147483647;` ` ` `$result` `= ` `$INT_MAX` `;` ` ` `// Sorting the array.` ` ` `sort(` `$arr` `, ` `$n` `);` ` ` `sort(` `$arr` `);` ` ` `// Find minimum value among` ` ` `// all K size subarray.` ` ` `for` `(` `$i` `= 0; ` `$i` `<= ` `$n` `- ` `$k` `; ` `$i` `++)` ` ` `$result` `= min(` `$result` `, ` `$arr` `[` `$i` `+ ` `$k` `- 1] -` ` ` `$arr` `[` `$i` `]);` ` ` `return` `$result` `;` `}` ` ` `// Driver Code` ` ` `$arr` `= ` `array` `(10, 100, 300, 200, 1000, 20, 30);` ` ` `$n` `= sizeof(` `$arr` `);` ` ` `$k` `= 3;` ` ` `echo` `minDiff(` `$arr` `, ` `$n` `, ` `$k` `);` ` ` `// This code is contributed by nitin mittal.` `?>` |

## Javascript

`<script>` `// javascript program to find minimum difference` `// of maximum and minimum of K number.` ` ` `// Return minimum difference of` ` ` `// maximum and minimum of k` ` ` `// elements of arr[0..n-1].` ` ` `function` `minDiff(arr , n , k) {` ` ` `var` `result = Number.MAX_VALUE;` ` ` `// Sorting the array.` ` ` `arr.sort((a,b)=>a-b);` ` ` `// Find minimum value among` ` ` `// all K size subarray.` ` ` `for` `(i = 0; i <= n - k; i++)` ` ` `result = Math.min(result, arr[i + k - 1] - arr[i]);` ` ` `return` `result;` ` ` `}` ` ` `// Driver code` ` ` ` ` `var` `arr = [ 10, 100, 300, 200, 1000, 20, 30 ];` ` ` `var` `n = arr.length;` ` ` `var` `k = 3;` ` ` `document.write(minDiff(arr, n, k));` `// This code contributed by gauravrajput1` `</script>` |

**Output**

20

**Time Complexity: O(nlogn).****Auxiliary Space: O(1)**

This article is contributed by **Anuj Chauhan**. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.