Minimize the maximum difference between adjacent elements in an array

Last Updated : 12 Jul, 2025

Given a non-decreasing array arr[] and an integer k, find the minimum possible value of the maximum difference between adjacent elements after removing k elements from the array.
Note: k < n - 2.

Examples:

Input: arr[] = [3, 7, 8, 10, 14], k = 2
Output: 2
Explanation: After removing elements arr[0] and arr[4], the remaining array is [7, 8, 10]. The maximum difference between adjacent elements is 2 which is minimum.
Input: arr[] = [12, 16, 22, 31, 31, 38], k = 3
Output: 6
Explanation: After removing elements arr[3], arr[4] and arr[5], the remaining array is [12, 16, 22]. The maximum difference between adjacent elements is 6 which is minimum.

Table of Content

[Naive Approach] Generating All Subsets - O(n * 2^n) time and O(n-k) space

The idea is to generate all possible subsets of size n-k from the original array and find the subset that has the minimum maximum difference between adjacent elements.

C++

#include <bits/stdc++.h> using namespace std; int maxDiff(vector<int>& subset) {  int maxDiff = 0;  for (int i = 1; i < subset.size(); i++) {  maxDiff = max(maxDiff, subset[i] - subset[i-1]);  }  return maxDiff; } // Recursive function to generate all subsets // of size n - k. void minDiffRecur(vector<int>& arr, int i,  vector<int>& curr, int k, int& minDiff) {  if (curr.size() == k) {  minDiff = min(minDiff, maxDiff(curr));  return;  }    if (i == arr.size()) {  return;  }    // Include current element  curr.push_back(arr[i]);  minDiffRecur(arr, i + 1, curr, k, minDiff);  curr.pop_back();    // Exclude current element  minDiffRecur(arr, i + 1, curr, k, minDiff); } // Function to find the minimum adjacent  // difference in an array after k removals. int minDiff(vector<int> &arr, int k) {  int n = arr.size();  vector<int> curr;  int minDiff = INT_MAX;    minDiffRecur(arr, 0, curr, n - k, minDiff);  return minDiff; } int main() {  vector<int> arr = {3, 7, 8, 10, 14};  int k = 2;  cout << minDiff(arr, k);  return 0; }

Java

import java.util.ArrayList; class GfG {    // Function to find the maximum adjacent   // difference in an array.  static int maxDiff(ArrayList<Integer> subset) {  int maxDiff = 0;  for (int i = 1; i < subset.size(); i++) {  maxDiff = Math.max(maxDiff, subset.get(i) - subset.get(i-1));  }  return maxDiff;  }  // Recursive function to generate all subsets  // of size n - k.  static void minDiffRecur(int[] arr, int i,   ArrayList<Integer> curr, int k, int[] minDiff) {  if (curr.size() == k) {  minDiff[0] = Math.min(minDiff[0], maxDiff(curr));  return;  }    if (i == arr.length) {  return;  }    // Include current element  curr.add(arr[i]);  minDiffRecur(arr, i + 1, curr, k, minDiff);  curr.remove(curr.size() - 1);    // Exclude current element  minDiffRecur(arr, i + 1, curr, k, minDiff);  }  // Function to find the minimum adjacent   // difference in an array after k removals.  static int minDiff(int[] arr, int k) {  int n = arr.length;  ArrayList<Integer> curr = new ArrayList<>();  int[] minDiff = {Integer.MAX_VALUE};    minDiffRecur(arr, 0, curr, n - k, minDiff);  return minDiff[0];  }  public static void main(String[] args) {  int[] arr = {3, 7, 8, 10, 14};  int k = 2;  System.out.println(minDiff(arr, k));  } }

Python

def maxDiff(subset): maxDiff = 0 for i in range(1, len(subset)): maxDiff = max(maxDiff, subset[i] - subset[i-1]) return maxDiff # Recursive function to generate all subsets # of size n - k. def minDiffRecur(arr, i, curr, k, minDiff): if len(curr) == k: minDiff[0] = min(minDiff[0], maxDiff(curr)) return if i == len(arr): return # Include current element curr.append(arr[i]) minDiffRecur(arr, i + 1, curr, k, minDiff) curr.pop() # Exclude current element minDiffRecur(arr, i + 1, curr, k, minDiff) # Function to find the minimum adjacent  # difference in an array after k removals. def minDiff(arr, k): n = len(arr) curr = [] minDiff = [float('inf')] minDiffRecur(arr, 0, curr, n - k, minDiff) return minDiff[0] if __name__ == "__main__": arr = [3, 7, 8, 10, 14] k = 2 print(minDiff(arr, k))

using System; using System.Collections.Generic; class GfG {    // Function to find the maximum adjacent   // difference in an array.  static int MaxDiff(List<int> subset) {  int maxDiff = 0;  for (int i = 1; i < subset.Count; i++) {  maxDiff = Math.Max(maxDiff, subset[i] - subset[i-1]);  }  return maxDiff;  }  // Recursive function to generate all subsets  // of size n - k.  static void MinDiffRecur(int[] arr, int i,   List<int> curr, int k, ref int minDiff) {  if (curr.Count == k) {  minDiff = Math.Min(minDiff, MaxDiff(curr));  return;  }    if (i == arr.Length) {  return;  }    // Include current element  curr.Add(arr[i]);  MinDiffRecur(arr, i + 1, curr, k, ref minDiff);  curr.RemoveAt(curr.Count - 1);    // Exclude current element  MinDiffRecur(arr, i + 1, curr, k, ref minDiff);  }  // Function to find the minimum adjacent   // difference in an array after k removals.  static int MinDiff(int[] arr, int k) {  int n = arr.Length;  List<int> curr = new List<int>();  int minDiff = int.MaxValue;    MinDiffRecur(arr, 0, curr, n - k, ref minDiff);  return minDiff;  }  static void Main() {  int[] arr = {3, 7, 8, 10, 14};  int k = 2;  Console.WriteLine(MinDiff(arr, k));  } }

JavaScript

function maxDiff(subset) {  let maxDiff = 0;  for (let i = 1; i < subset.length; i++) {  maxDiff = Math.max(maxDiff, subset[i] - subset[i-1]);  }  return maxDiff; } // Recursive function to generate all subsets // of size n - k. function minDiffRecur(arr, i, curr, k, minDiff) {  if (curr.length === k) {  minDiff[0] = Math.min(minDiff[0], maxDiff(curr));  return;  }    if (i === arr.length) {  return;  }    // Include current element  curr.push(arr[i]);  minDiffRecur(arr, i + 1, curr, k, minDiff);  curr.pop();    // Exclude current element  minDiffRecur(arr, i + 1, curr, k, minDiff); } // Function to find the minimum adjacent  // difference in an array after k removals. function minDiff(arr, k) {  let n = arr.length;  let curr = [];  let minDiff = [Infinity];    minDiffRecur(arr, 0, curr, n - k, minDiff);  return minDiff[0]; } let arr = [3, 7, 8, 10, 14]; let k = 2; console.log(minDiff(arr, k));

Output

[Better Approach] Removing Elements from Ends - O(n * k) time and O(n) space

The idea is to observe that removing middle elements from a sorted array generally increases the maximum difference between adjacent elements, so we should focus on removing elements from the ends.

Step by step approach:

Try different combinations of removing i elements from start and k-i elements from end.
For each combination, calculate the maximum difference between adjacent elements.
Track the minimum of all these maximum differences.
Return the minimum maximum difference found.

C++

#include <bits/stdc++.h> using namespace std; int minDiff(vector<int> &arr, int k) {  int n = arr.size();  int res = INT_MAX;    // Try removing i elements from start   // and k-i elements from end  for (int i = 0; i <= k; i++) {    // Calculate maximum difference after removal  int maxDiff = 0;  vector<int> curr;    // Create new array after removals  for (int j = i; j < n - (k - i); j++) {  curr.push_back(arr[j]);  }    // Calculate maximum difference  for (int j = 1; j < curr.size(); j++) {  maxDiff = max(maxDiff, curr[j] - curr[j-1]);  }    res = min(res, maxDiff);  }    return res; } int main() {  vector<int> arr = {3, 7, 8, 10, 14};  int k = 2;  cout << minDiff(arr, k);  return 0; }

Java

import java.util.ArrayList; class GfG {    static int minDiff(int[] arr, int k) {  int n = arr.length;  int res = Integer.MAX_VALUE;    // Try removing i elements from start   // and k-i elements from end  for (int i = 0; i <= k; i++) {    // Calculate maximum difference after removal  int maxDiff = 0;  ArrayList<Integer> curr = new ArrayList<>();    // Create new array after removals  for (int j = i; j < n - (k - i); j++) {  curr.add(arr[j]);  }    // Calculate maximum difference  for (int j = 1; j < curr.size(); j++) {  maxDiff = Math.max(maxDiff, curr.get(j) - curr.get(j-1));  }    res = Math.min(res, maxDiff);  }    return res;  }  public static void main(String[] args) {  int[] arr = {3, 7, 8, 10, 14};  int k = 2;  System.out.println(minDiff(arr, k));  } }

Python

def minDiff(arr, k): n = len(arr) res = float('inf') # Try removing i elements from start  # and k-i elements from end for i in range(k + 1): # Calculate maximum difference after removal maxDiff = 0 curr = [] # Create new array after removals for j in range(i, n - (k - i)): curr.append(arr[j]) # Calculate maximum difference for j in range(1, len(curr)): maxDiff = max(maxDiff, curr[j] - curr[j-1]) res = min(res, maxDiff) return res if __name__ == "__main__": arr = [3, 7, 8, 10, 14] k = 2 print(minDiff(arr, k))

using System; using System.Collections.Generic; class GfG {    static int minDiff(int[] arr, int k) {  int n = arr.Length;  int res = int.MaxValue;    // Try removing i elements from start   // and k-i elements from end  for (int i = 0; i <= k; i++) {    // Calculate maximum difference after removal  int maxDiff = 0;  List<int> curr = new List<int>();    // Create new array after removals  for (int j = i; j < n - (k - i); j++) {  curr.Add(arr[j]);  }    // Calculate maximum difference  for (int j = 1; j < curr.Count; j++) {  maxDiff = Math.Max(maxDiff, curr[j] - curr[j-1]);  }    res = Math.Min(res, maxDiff);  }    return res;  }  static void Main() {  int[] arr = {3, 7, 8, 10, 14};  int k = 2;  Console.WriteLine(minDiff(arr, k));  } }

JavaScript

function minDiff(arr, k) {  let n = arr.length;  let res = Infinity;    // Try removing i elements from start   // and k-i elements from end  for (let i = 0; i <= k; i++) {    // Calculate maximum difference after removal  let maxDiff = 0;  let curr = [];    // Create new array after removals  for (let j = i; j < n - (k - i); j++) {  curr.push(arr[j]);  }    // Calculate maximum difference  for (let j = 1; j < curr.length; j++) {  maxDiff = Math.max(maxDiff, curr[j] - curr[j-1]);  }    res = Math.min(res, maxDiff);  }    return res; } let arr = [3, 7, 8, 10, 14]; let k = 2; console.log(minDiff(arr, k));

Output

[Efficient Approach] Using Deque and Sliding Window - O(n) time and O(n) space

The idea is to find a contiguous subarray of length (n-k-1) from the difference array that has the minimum maximum value, which corresponds to the optimal set of elements to keep after removing k elements from the original array.

Step by step approach:

Create a difference array where diff[i] = arr[i+1] - arr[i].
Use a sliding window of size (n-k-1) on the difference array.
Maintain a monotonic deque to track the maximum value in each window.
Remove smaller elements from back as they can't be the maximum in current window.
Remove elements from front that fall outside current window.
Track the minimum of these window maximums as the final result.

Refer to Sliding Window Maximum (Maximum of all subarrays of size K) for detailed explanation on sliding window.

C++

#include <bits/stdc++.h> using namespace std; // Function to find the minimum adjacent  // difference in an array after k removals. int minDiff(vector<int> &arr, int k) {  int n = arr.size();    // Create a difference array  vector<int> diff(n - 1);  for (int i = 0; i < n - 1; i++) {  diff[i] = arr[i + 1] - arr[i];  }    // We need to find a window of size (n-k-1)  // with minimum maximum difference  int windowSize = n - k - 1;  int result = INT_MAX;    // Use a deque to maintain a monotonic  // queue of potential maximums  deque<int> dq;    // Process the first window  for (int i = 0; i < windowSize; i++) {    // Remove smaller elements from back   // as they won't be the maximum  while (!dq.empty() && diff[i] >= diff[dq.back()]) {  dq.pop_back();  }  dq.push_back(i);  }    // Process the rest of the array  for (int i = windowSize; i < n - 1; i++) {    // Get the maximum of the current window  result = min(result, diff[dq.front()]);    // Remove elements outside the current window  while (!dq.empty() && dq.front() <= i - windowSize) {  dq.pop_front();  }    // Remove smaller elements from back   // as they won't be the maximum  while (!dq.empty() && diff[i] >= diff[dq.back()]) {  dq.pop_back();  }    dq.push_back(i);  }    // Check the last window  result = min(result, diff[dq.front()]);    return result; } int main() {  vector<int> arr = {3, 7, 8, 10, 14};  int k = 2;  cout << minDiff(arr, k);  return 0; }

Java

import java.util.ArrayDeque; import java.util.Deque; class GfG {    // Function to find the minimum adjacent   // difference in an array after k removals.  static int minDiff(int[] arr, int k) {  int n = arr.length;    // Create a difference array  int[] diff = new int[n - 1];  for (int i = 0; i < n - 1; i++) {  diff[i] = arr[i + 1] - arr[i];  }    // We need to find a window of size (n-k-1)  // with minimum maximum difference  int windowSize = n - k - 1;  int result = Integer.MAX_VALUE;    // Use a deque to maintain a monotonic  // queue of potential maximums  Deque<Integer> dq = new ArrayDeque<>();    // Process the first window  for (int i = 0; i < windowSize; i++) {    // Remove smaller elements from back   // as they won't be the maximum  while (!dq.isEmpty() && diff[i] >= diff[dq.peekLast()]) {  dq.pollLast();  }  dq.offerLast(i);  }    // Process the rest of the array  for (int i = windowSize; i < n - 1; i++) {    // Get the maximum of the current window  result = Math.min(result, diff[dq.peekFirst()]);    // Remove elements outside the current window  while (!dq.isEmpty() && dq.peekFirst() <= i - windowSize) {  dq.pollFirst();  }    // Remove smaller elements from back   // as they won't be the maximum  while (!dq.isEmpty() && diff[i] >= diff[dq.peekLast()]) {  dq.pollLast();  }    dq.offerLast(i);  }    // Check the last window  result = Math.min(result, diff[dq.peekFirst()]);    return result;  }  public static void main(String[] args) {  int[] arr = {3, 7, 8, 10, 14};  int k = 2;  System.out.println(minDiff(arr, k));  } }

Python

from collections import deque def minDiff(arr, k): n = len(arr) # Create a difference array diff = [arr[i + 1] - arr[i] for i in range(n - 1)] # We need to find a window of size (n-k-1) # with minimum maximum difference windowSize = n - k - 1 result = float('inf') # Use a deque to maintain a monotonic # queue of potential maximums dq = deque() # Process the first window for i in range(windowSize): # Remove smaller elements from back  # as they won't be the maximum while dq and diff[i] >= diff[dq[-1]]: dq.pop() dq.append(i) # Process the rest of the array for i in range(windowSize, n - 1): # Get the maximum of the current window result = min(result, diff[dq[0]]) # Remove elements outside the current window while dq and dq[0] <= i - windowSize: dq.popleft() # Remove smaller elements from back  # as they won't be the maximum while dq and diff[i] >= diff[dq[-1]]: dq.pop() dq.append(i) # Check the last window result = min(result, diff[dq[0]]) return result if __name__ == "__main__": arr = [3, 7, 8, 10, 14] k = 2 print(minDiff(arr, k))

using System; using System.Collections.Generic; class GfG {    // Function to find the minimum adjacent   // difference in an array after k removals.  static int minDiff(int[] arr, int k) {  int n = arr.Length;    // Create a difference array  int[] diff = new int[n - 1];  for (int i = 0; i < n - 1; i++) {  diff[i] = arr[i + 1] - arr[i];  }    // We need to find a window of size (n-k-1)  // with minimum maximum difference  int windowSize = n - k - 1;  int result = int.MaxValue;    // Use a deque to maintain a monotonic  // queue of potential maximums  LinkedList<int> dq = new LinkedList<int>();    // Process the first window  for (int i = 0; i < windowSize; i++) {    // Remove smaller elements from back   // as they won't be the maximum  while (dq.Count > 0 && diff[i] >= diff[dq.Last.Value]) {  dq.RemoveLast();  }  dq.AddLast(i);  }    // Process the rest of the array  for (int i = windowSize; i < n - 1; i++) {    // Get the maximum of the current window  result = Math.Min(result, diff[dq.First.Value]);    // Remove elements outside the current window  while (dq.Count > 0 && dq.First.Value <= i - windowSize) {  dq.RemoveFirst();  }    // Remove smaller elements from back   // as they won't be the maximum  while (dq.Count > 0 && diff[i] >= diff[dq.Last.Value]) {  dq.RemoveLast();  }    dq.AddLast(i);  }    // Check the last window  result = Math.Min(result, diff[dq.First.Value]);    return result;  }  static void Main() {  int[] arr = {3, 7, 8, 10, 14};  int k = 2;  Console.WriteLine(minDiff(arr, k));  } }

JavaScript

function minDiff(arr, k) {  let n = arr.length;    // Create a difference array  let diff = new Array(n - 1);  for (let i = 0; i < n - 1; i++) {  diff[i] = arr[i + 1] - arr[i];  }    // We need to find a window of size (n-k-1)  // with minimum maximum difference  let windowSize = n - k - 1;  let result = Infinity;    // Use a deque to maintain a monotonic  // queue of potential maximums  let dq = [];    // Process the first window  for (let i = 0; i < windowSize; i++) {    // Remove smaller elements from back   // as they won't be the maximum  while (dq.length > 0 && diff[i] >= diff[dq[dq.length - 1]]) {  dq.pop();  }  dq.push(i);  }    // Process the rest of the array  for (let i = windowSize; i < n - 1; i++) {    // Get the maximum of the current window  result = Math.min(result, diff[dq[0]]);    // Remove elements outside the current window  while (dq.length > 0 && dq[0] <= i - windowSize) {  dq.shift();  }    // Remove smaller elements from back   // as they won't be the maximum  while (dq.length > 0 && diff[i] >= diff[dq[dq.length - 1]]) {  dq.pop();  }    dq.push(i);  }    // Check the last window  result = Math.min(result, diff[dq[0]]);    return result; } let arr = [3, 7, 8, 10, 14]; let k = 2; console.log(minDiff(arr, k));