# Minimize difference between maximum and minimum of Array by at most K replacements

Given an array **arr[] **and an** **integer **K**, that task is to choose **at most K elements** of the array and replace it by any number. Find the minimum difference between the maximum and minimum value of the array after performing **at most K replacement.**

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:arr[] = {1, 4, 6, 11, 15}, k = 3Output:2Explanation:

k = 1, arr = {4, 4, 6, 11, 15}, arr[0] replaced by 4

k = 2, arr = {4, 4, 6, 4, 15}, arr[3] replaced by 4

k = 3, arr = {4, 4, 6, 4, 4}, arr[4] replaced by 4

Max – Min = 6 – 4 = 2

Input:arr[] = {1, 4, 6, 11, 15}, k = 2Output:5Explanation:

k = 1, arr = {1, 4, 6, 6, 15}, arr[3] replaced by 6

k = 2, arr = {1, 4, 6, 6, 6}, arr[4] replaced by 6

Max – Min = 6 – 1 = 5

**Approach:** The idea is to use the concept of Two Pointers. Below are the steps:

- Sort the given array.
- Maintain two pointers, one pointing to the last element of the array and the other to the
**K**element of the array.^{th} - Iterate over the array
**K + 1**times and each time find the difference of the elements pointed by the two pointers. - Every time on finding the difference, keep track of the minimum possible difference in a variable and return that value at the end.

Below is the implementation of the above approach:

## C++

`// C++ program of the approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to find minimum difference` `// between the maximum and the minimum` `// elements arr[] by at most K replacements` `int` `maxMinDifference(` `int` `arr[], ` `int` `n, ` `int` `k)` `{` ` ` `// Check if turns are more than` ` ` `// or equal to n-1 then simply` ` ` `// return zero` ` ` `if` `(k >= n - 1)` ` ` `return` `0;` ` ` `// Sort the array` ` ` `sort(arr, arr + n);` ` ` `// Set difference as the` ` ` `// maximum possible difference` ` ` `int` `ans = arr[n - 1] - arr[0];` ` ` `// Iterate over the array to` ` ` `// track the minimum difference` ` ` `// in k turns` ` ` `for` `(` `int` `i = k, j = n - 1;` ` ` `i >= 0; --i, --j) {` ` ` `ans = min(arr[j] - arr[i], ans);` ` ` `}` ` ` `// Return the answer` ` ` `return` `ans;` `}` `// Driver Code` `int` `main()` `{` ` ` `// Given array arr[]` ` ` `int` `arr[] = { 1, 4, 6, 11, 15 };` ` ` `int` `N = ` `sizeof` `(arr) / ` `sizeof` `(arr[0]);` ` ` `// Given K replacements` ` ` `int` `K = 3;` ` ` `// Function Call` ` ` `cout << maxMinDifference(arr, N, K);` ` ` `return` `0;` `}` |

## Java

`// Java program of the approach` `import` `java.io.*;` `import` `java.util.Arrays;` `class` `GFG{` `// Function to find minimum difference` `// between the maximum and the minimum` `// elements arr[] by at most K replacements` `static` `int` `maxMinDifference(` `int` `arr[], ` `int` `n, ` `int` `k)` `{` ` ` `// Check if turns are more than` ` ` `// or equal to n-1 then simply` ` ` `// return zero` ` ` `if` `(k >= n - ` `1` `)` ` ` `return` `0` `;` ` ` `// Sort the array` ` ` `Arrays.sort(arr);` ` ` `// Set difference as the` ` ` `// maximum possible difference` ` ` `int` `ans = arr[n - ` `1` `] - arr[` `0` `];` ` ` `// Iterate over the array to` ` ` `// track the minimum difference` ` ` `// in k turns` ` ` `for` `(` `int` `i = k, j = n - ` `1` `;` ` ` `i >= ` `0` `; --i, --j)` ` ` `{` ` ` `ans = Math.min(arr[j] - arr[i], ans);` ` ` `}` ` ` `// Return the answer` ` ` `return` `ans;` `}` `// Driver Code` `public` `static` `void` `main(String[] args)` `{` ` ` `// Given array arr[]` ` ` `int` `arr[] = { ` `1` `, ` `4` `, ` `6` `, ` `11` `, ` `15` `};` ` ` `int` `N = arr.length;` ` ` `// Given K replacements` ` ` `int` `K = ` `3` `;` ` ` `// Function Call` ` ` `System.out.print(maxMinDifference(arr, N, K));` `}` `}` `// This code is contributed by shivanisinghss2110` |

## Python3

`# Python3 program for the above approach` `# Function to find minimum difference` `# between the maximum and the minimum` `# elements arr[] by at most K replacements` `def` `maxMinDifference(arr, n, k):` ` ` `# Check if turns are more than` ` ` `# or equal to n-1 then simply` ` ` `# return zero` ` ` `if` `(k >` `=` `n ` `-` `1` `):` ` ` `return` `0` ` ` `# Sort the array` ` ` `arr.sort()` ` ` `# Set difference as the` ` ` `# maximum possible difference` ` ` `ans ` `=` `arr[n ` `-` `1` `] ` `-` `arr[` `0` `]` ` ` `# Iterate over the array to` ` ` `# track the minimum difference` ` ` `# in k turns` ` ` `i ` `=` `k` ` ` `j ` `=` `n ` `-` `1` ` ` `while` `i >` `=` `0` `:` ` ` `ans ` `=` `min` `(arr[j] ` `-` `arr[i], ans)` ` ` `i ` `-` `=` `1` ` ` `j ` `-` `=` `1` ` ` `# Return the answer` ` ` `return` `ans` `# Driver code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` `# Given array arr[]` ` ` `arr ` `=` `[ ` `1` `, ` `4` `, ` `6` `, ` `11` `, ` `15` `]` ` ` `N ` `=` `len` `(arr)` ` ` `# Given K replacements` ` ` `K ` `=` `3` ` ` `# Function Call` ` ` `print` `(maxMinDifference(arr, N, K))` `# This code is contributed by Shivam Singh` |

## C#

`// C# program of the approach` `using` `System;` `class` `GFG{` ` ` `// Function to find minimum difference` `// between the maximum and the minimum` `// elements arr[] by at most K replacements` `static` `int` `maxMinDifference(` `int` `[]arr, ` `int` `n, ` `int` `k)` `{` ` ` `// Check if turns are more than` ` ` `// or equal to n-1 then simply` ` ` `// return zero` ` ` `if` `(k >= n - 1)` ` ` `return` `0;` ` ` ` ` `// Sort the array` ` ` `Array.Sort(arr);` ` ` ` ` `// Set difference as the` ` ` `// maximum possible difference` ` ` `int` `ans = arr[n - 1] - arr[0];` ` ` ` ` `// Iterate over the array to` ` ` `// track the minimum difference` ` ` `// in k turns` ` ` `for` `(` `int` `i = k, j = n - 1;` ` ` `i >= 0; --i, --j)` ` ` `{` ` ` `ans = Math.Min(arr[j] - arr[i], ans);` ` ` `}` ` ` ` ` `// Return the answer` ` ` `return` `ans;` `}` ` ` `// Driver Code` `public` `static` `void` `Main(` `string` `[] args)` `{` ` ` `// Given array arr[]` ` ` `int` `[] arr = ` `new` `int` `[] { 1, 4, 6, 11, 15 };` ` ` `int` `N = arr.Length;` ` ` ` ` `// Given K replacements` ` ` `int` `K = 3;` ` ` ` ` `// Function Call` ` ` `Console.Write(maxMinDifference(arr, N, K));` `}` `}` ` ` `// This code is contributed by Ritik Bansal` |

## Javascript

`<script>` `// Javascript program for the above approach` `// Function to find minimum difference` `// between the maximum and the minimum` `// elements arr[] by at most K replacements` `function` `maxMinDifference(arr, n, k)` `{` ` ` `// Check if turns are more than` ` ` `// or equal to n-1 then simply` ` ` `// return zero` ` ` `if` `(k >= n - 1)` ` ` `return` `0;` ` ` `// Sort the array` ` ` `arr.sort((a, b) => a - b);` ` ` `// Set difference as the` ` ` `// maximum possible difference` ` ` `let ans = arr[n - 1] - arr[0];` ` ` `// Iterate over the array to` ` ` `// track the minimum difference` ` ` `// in k turns` ` ` `for` `(let i = k, j = n - 1;` ` ` `i >= 0; --i, --j)` ` ` `{` ` ` `ans = Math.min(arr[j] - arr[i], ans);` ` ` `}` ` ` `// Return the answer` ` ` `return` `ans;` `}` `// Driver Code` ` ` ` ` `// Given array arr[]` ` ` `let arr = [ 1, 4, 6, 11, 15 ];` ` ` `let N = arr.length;` ` ` `// Given K replacements` ` ` `let K = 3;` ` ` `// Function Call` ` ` `document.write(maxMinDifference(arr, N, K));` ` ` `</script>` |

**Output:**

2

**Time Complexity:** *O(N*log _{2}N)*

**Auxiliary Space:**

*O(1)*