Given an array arr[] consisting of N integers and an integer K, the task is to find the minimum difference between the maximum and minimum element present in the array after removing any subarray of size K.
Examples:
Input: arr[] = {4, 5, 8, 9, 1, 2}, K = 2
Output: 4
Explanation: Remove the subarray {8, 9}. The minimum difference between maximum and minimum array elements becomes (5 – 1) = 4.Input: arr[] = {1, 2, 2}, K = 1
Output: 0
Explanation: Remove subarray {1}. The minimum difference between maximum and minimum array elements becomes (2 – 2) = 0.
Naive Approach: The simplest approach is to remove all possible subarrays of size K one by one and calculate the difference between maximum and minimum among the remaining elements. Finally, print the minimum difference obtained.
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized by storing maximum and minimum prefixes upto any index and storing the maximum and minimum suffixes starting from any index. Once the above four values are calculated, find the maximum and minimum array elements after removing a K-length subarray in constant computational complexity.Â
Follow the steps below to solve the problem:
- Initialize arrays maxSufix[] and minSuffix[]. such that ith element of maxSuffix[] and minSuffix[] array denotes the maximum and minimum elements respectively present at the right of the ith index.
- Initialize two variables, say maxPrefix and minPrefix, to store the maximum and minimum elements present in the prefix subarray.
- Traverse the array over the indices [1, N] and check if i + K <= N or not. If found to be true, then perform the following steps:
- The maximum value present in the array after removing a subarray of size K starting from ith index is max(maxSuffix[i + k], maxPrefix).
- The minimum value present in the array after removing a subarray of size K starting from ith index is min(minSuffix[i + k], minPrefix).
- Update minDiff to min( minDiff, maximum – minimum), to store the minimum difference.
- Print minDiff as the required answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approachÂ
#include <bits/stdc++.h>using namespace std;Â
// Function to minimize difference// between maximum and minimum array// elements by removing a K-length subarrayvoid minimiseDifference(vector<int>& arr, int K){    // Size of array    int N = arr.size();Â
    // Stores the maximum and minimum    // in the suffix subarray [i .. N-1]    int maxSuffix[N + 1], minSuffix[N + 1];Â
    maxSuffix[N] = -1e9;    minSuffix[N] = 1e9;    maxSuffix[N - 1] = arr[N - 1];    minSuffix[N - 1] = arr[N - 1];Â
    // Constructing the maxSuffix and    // minSuffix arraysÂ
    // Traverse the array    for (int i = N - 2; i >= 0; --i) {Â
        maxSuffix[i] = max(maxSuffix[i + 1], arr[i]);        minSuffix[i] = min(minSuffix[i + 1], arr[i]);    }Â
    // Stores the maximum and minimum    // in the prefix subarray [0 .. i-1]    int maxPrefix = arr[0];    int minPrefix = arr[0];Â
    // Store the minimum difference    int minDiff = maxSuffix[K] - minSuffix[K];Â
    // Traverse the array    for (int i = 1; i < N; ++i) {Â
        // If the suffix doesn't exceed        // the end of the array        if (i + K <= N) {Â
            // Store the maximum element            // in array after removing            // subarray of size K            int maximum = max(maxSuffix[i + K], maxPrefix);Â
            // Stores the maximum element            // in array after removing            // subarray of size K            int minimum = min(minSuffix[i + K], minPrefix);Â
            // Update minimum difference            minDiff = min(minDiff, maximum - minimum);        }Â
        // Updating the maxPrefix and        // minPrefix with current element        maxPrefix = max(maxPrefix, arr[i]);        minPrefix = min(minPrefix, arr[i]);    }Â
    // Print the minimum difference    cout << minDiff << "\n";}Â
// Driver Codeint main(){Â Â Â Â vector<int> arr = { 4, 5, 8, 9, 1, 2 };Â Â Â Â int K = 2;Â Â Â Â minimiseDifference(arr, K);Â
    return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{Â
  // Function to minimize difference  // between maximum and minimum array  // elements by removing a K-length subarray  static void minimiseDifference(int[] arr, int K)  {    // Size of array    int N = arr.length;Â
    // Stores the maximum and minimum    // in the suffix subarray [i .. N-1]    int[] maxSuffix = new int[N + 1];    int[] minSuffix = new int[N + 1];Â
    maxSuffix[N] = -1000000000;    minSuffix[N] = 1000000000;    maxSuffix[N - 1] = arr[N - 1];    minSuffix[N - 1] = arr[N - 1];Â
    // Constructing the maxSuffix and    // minSuffix arraysÂ
    // Traverse the array    for (int i = N - 2; i >= 0; --i) {Â
      maxSuffix[i]        = Math.max(maxSuffix[i + 1], arr[i]);      minSuffix[i]        = Math.min(minSuffix[i + 1], arr[i]);    }Â
    // Stores the maximum and minimum    // in the prefix subarray [0 .. i-1]    int maxPrefix = arr[0];    int minPrefix = arr[0];Â
    // Store the minimum difference    int minDiff = maxSuffix[K] - minSuffix[K];Â
    // Traverse the array    for (int i = 1; i < N; ++i) {Â
      // If the suffix doesn't exceed      // the end of the array      if (i + K <= N) {Â
        // Store the maximum element        // in array after removing        // subarray of size K        int maximum          = Math.max(maxSuffix[i + K], maxPrefix);Â
        // Stores the maximum element        // in array after removing        // subarray of size K        int minimum          = Math.min(minSuffix[i + K], minPrefix);Â
        // Update minimum difference        minDiff          = Math.min(minDiff, maximum - minimum);      }Â
      // Updating the maxPrefix and      // minPrefix with current element      maxPrefix = Math.max(maxPrefix, arr[i]);      minPrefix = Math.min(minPrefix, arr[i]);    }Â
    // Print the minimum difference    System.out.print(minDiff);  }Â
  // Driver Code  public static void main(String[] args)  {    int[] arr = { 4, 5, 8, 9, 1, 2 };    int K = 2;    minimiseDifference(arr, K);  }}Â
// This code is contributed by susmitakundugoaldanga. |
Python3
# Python 3 program for the above approachÂ
# Function to minimize difference# between maximum and minimum array# elements by removing a K-length subarraydef minimiseDifference(arr, K):       # Size of array    N = len(arr)Â
    # Stores the maximum and minimum    # in the suffix subarray [i .. N-1]    maxSuffix = [0 for i in range(N + 1)]    minSuffix = [0 for i in range(N + 1)]Â
    maxSuffix[N] = -1e9    minSuffix[N] = 1e9    maxSuffix[N - 1] = arr[N - 1]    minSuffix[N - 1] = arr[N - 1]Â
    # Constructing the maxSuffix and    # minSuffix arraysÂ
    # Traverse the array    i = N - 2    while(i >= 0):        maxSuffix[i] = max(maxSuffix[i + 1],arr[i])        minSuffix[i] = min(minSuffix[i + 1], arr[i])        i -= 1Â
    # Stores the maximum and minimum    # in the prefix subarray [0 .. i-1]    maxPrefix = arr[0]    minPrefix = arr[0]Â
    # Store the minimum difference    minDiff = maxSuffix[K] - minSuffix[K]Â
    # Traverse the array    for i in range(1, N):               # If the suffix doesn't exceed        # the end of the array        if (i + K <= N):                       # Store the maximum element            # in array after removing            # subarray of size K            maximum = max(maxSuffix[i + K], maxPrefix)Â
            # Stores the maximum element            # in array after removing            # subarray of size K            minimum = min(minSuffix[i + K], minPrefix)Â
            # Update minimum difference            minDiff = min(minDiff, maximum - minimum)Â
        # Updating the maxPrefix and        # minPrefix with current element        maxPrefix = max(maxPrefix, arr[i])        minPrefix = min(minPrefix, arr[i])Â
    # Print the minimum difference    print(minDiff)Â
# Driver Codeif __name__ == '__main__':Â Â Â Â arr =Â [4, 5, 8, 9, 1, 2]Â Â Â Â K = 2Â Â Â Â minimiseDifference(arr, K)Â Â Â Â Â Â Â Â Â # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFg {Â
  // Function to minimize difference  // between maximum and minimum array  // elements by removing a K-length subarray  static void minimiseDifference(List<int> arr, int K)  {    // Size of array    int N = arr.Count;Â
    // Stores the maximum and minimum    // in the suffix subarray [i .. N-1]    int[] maxSuffix = new int[N + 1];    int[] minSuffix = new int[N + 1];Â
    maxSuffix[N] = -1000000000;    minSuffix[N] = 1000000000;    maxSuffix[N - 1] = arr[N - 1];    minSuffix[N - 1] = arr[N - 1];Â
    // Constructing the maxSuffix and    // minSuffix arraysÂ
    // Traverse the array    for (int i = N - 2; i >= 0; --i) {Â
      maxSuffix[i]        = Math.Max(maxSuffix[i + 1], arr[i]);      minSuffix[i]        = Math.Min(minSuffix[i + 1], arr[i]);    }Â
    // Stores the maximum and minimum    // in the prefix subarray [0 .. i-1]    int maxPrefix = arr[0];    int minPrefix = arr[0];Â
    // Store the minimum difference    int minDiff = maxSuffix[K] - minSuffix[K];Â
    // Traverse the array    for (int i = 1; i < N; ++i) {Â
      // If the suffix doesn't exceed      // the end of the array      if (i + K <= N) {Â
        // Store the maximum element        // in array after removing        // subarray of size K        int maximum          = Math.Max(maxSuffix[i + K], maxPrefix);Â
        // Stores the maximum element        // in array after removing        // subarray of size K        int minimum          = Math.Min(minSuffix[i + K], minPrefix);Â
        // Update minimum difference        minDiff          = Math.Min(minDiff, maximum - minimum);      }Â
      // Updating the maxPrefix and      // minPrefix with current element      maxPrefix = Math.Max(maxPrefix, arr[i]);      minPrefix = Math.Min(minPrefix, arr[i]);    }Â
    // Print the minimum difference    Console.WriteLine(minDiff);  }Â
  // Driver Code  public static void Main()  {    List<int> arr      = new List<int>() { 4, 5, 8, 9, 1, 2 };    int K = 2;    minimiseDifference(arr, K);  }}Â
// This code is contributed by chitranayal. |
Javascript
<script>Â
// JavaScript program for the above approachÂ
// Function to minimize difference// between maximum and minimum array// elements by removing a K-length subarrayfunction minimiseDifference(arr, K){    // Size of array    var N = arr.length;Â
    // Stores the maximum and minimum    // in the suffix subarray [i .. N-1]    var maxSuffix = new Array(N + 1);    var minSuffix = new Array(N + 1);Â
    maxSuffix[N] = -1e9;    minSuffix[N] = 1e9;    maxSuffix[N - 1] = arr[N - 1];    minSuffix[N - 1] = arr[N - 1];Â
    // Constructing the maxSuffix and    // minSuffix arraysÂ
    // Traverse the array    for (var i = N - 2; i >= 0; --i) {Â
        maxSuffix[i] = Math.max(maxSuffix[i + 1], arr[i]);        minSuffix[i] = Math.min(minSuffix[i + 1], arr[i]);    }Â
    // Stores the maximum and minimum    // in the prefix subarray [0 .. i-1]    var maxPrefix = arr[0];    var minPrefix = arr[0];Â
    // Store the minimum difference    var minDiff = maxSuffix[K] - minSuffix[K];Â
    // Traverse the array    for (var i = 1; i < N; ++i) {Â
        // If the suffix doesn't exceed        // the end of the array        if (i + K <= N) {Â
            // Store the maximum element            // in array after removing            // subarray of size K            var maximum =             Math.max(maxSuffix[i + K], maxPrefix);Â
            // Stores the maximum element            // in array after removing            // subarray of size K            var minimum =             Math.min(minSuffix[i + K], minPrefix);Â
            // Update minimum difference            minDiff =            Math.min(minDiff, maximum - minimum);        }Â
        // Updating the maxPrefix and        // minPrefix with current element        maxPrefix = Math.max(maxPrefix, arr[i]);        minPrefix = Math.min(minPrefix, arr[i]);    }Â
    // Print the minimum difference   document.write( minDiff + "<br>");}Â
Â
var arr = [ 4, 5, 8, 9, 1, 2 ];var K = 2;minimiseDifference(arr, K);Â
// This code is contributed by SoumikMondalÂ
</script> |
Â
Â
4
Time Complexity: O(N)
Auxiliary Space: O(N)Â
Related Topic: Subarrays, Subsequences, and Subsets in Array
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

… [Trackback]
[…] Read More here to that Topic: geeksforgeeks.org/minimize-difference-between-maximum-and-minimum-array-elements-by-removing-a-k-length-subarray/ […]
… [Trackback]
[…] Info on that Topic: geeksforgeeks.org/minimize-difference-between-maximum-and-minimum-array-elements-by-removing-a-k-length-subarray/ […]
… [Trackback]
[…] Information on that Topic: geeksforgeeks.org/minimize-difference-between-maximum-and-minimum-array-elements-by-removing-a-k-length-subarray/ […]
… [Trackback]
[…] Here you can find 47545 additional Info to that Topic: geeksforgeeks.org/minimize-difference-between-maximum-and-minimum-array-elements-by-removing-a-k-length-subarray/ […]
… [Trackback]
[…] Find More Info here to that Topic: geeksforgeeks.org/minimize-difference-between-maximum-and-minimum-array-elements-by-removing-a-k-length-subarray/ […]