Min difference between maximum and minimum element in all Y size subarrays
Last Updated : 29 Mar, 2023
Given an array arr[] of size N and integer Y, the task is to find a minimum of all the differences between the maximum and minimum elements in all the sub-arrays of size Y.
Examples:
Input: arr[] = { 3, 2, 4, 5, 6, 1, 9 } Y = 3
Output: 2
Explanation:
All subarrays of length = 3 are:
{3, 2, 4} where maximum element = 4 and minimum element = 2 difference = 2
{2, 4, 5} where maximum element = 5 and minimum element = 2 difference = 3
{4, 5, 6} where maximum element = 6 and minimum element = 4 difference = 2
{5, 6, 1} where maximum element = 6 and minimum element = 1 difference = 5
{6, 1, 9} where maximum element = 9 and minimum element = 6 difference = 3
Out of these, the minimum is 2.
Input: arr[] = { 1, 2, 3, 3, 2, 2 } Y = 4
Output: 1
Explanation:
All subarrays of length = 4 are:
{1, 2, 3, 3} maximum element = 3 and minimum element = 1 difference = 2
{2, 3, 3, 2} maximum element = 3 and minimum element = 2 difference = 1
{3, 3, 2, 2} maximum element = 3 and minimum element = 2 difference = 1
Out of these, the minimum is 1.
Naive Approach: The naive idea is to traverse for every index i in the range [0, N - Y] use another loop to traverse from ith index to (i + Y - 1)th index and then calculate the minimum and maximum elements in a subarray of size Y and hence calculate the difference of maximum and minimum element for that ith iteration. Finally, by keeping a check on differences, evaluate the minimum difference.
C++ #include<bits/stdc++.h> using namespace std; // function to calculate the Min difference //between maximum and minimum element //in all Y size subarrays int max_difference(int* arr, int N, int Y) { // variable to store Min difference //between maximum and minimum element/ int ans = INT_MAX; for (int i = 0; i <= N - Y; i++) { int maxi = INT_MIN; int mini = INT_MAX; for (int j = i; j <= i + Y - 1; j++) { maxi = max(maxi, arr[j]);// finding the maximum element. mini = min(mini, arr[j]);// finding the minimum element. } ans = min(ans, maxi -mini); } return ans;//returning the final answer. } // Driver Code int main() { // Given array arr[] int arr[] = { 1, 2, 3, 3, 2, 2 }; int N = sizeof arr / sizeof arr[0]; // Given subarray size int Y = 4; // Function Call cout << max_difference(arr, N, Y); return 0; } import sys # function to calculate the Min difference #between maximum and minimum element #in all Y size subarrays def max_difference(arr, N, Y): # variable to store Min difference #between maximum and minimum element/ ans = sys.maxsize; for i in range(0,N-Y+1): maxi = -sys.maxsize; mini = sys.maxsize; for j in range (i,i+Y): maxi = max(maxi, arr[j]);# finding the maximum element. mini = min(mini, arr[j]);# finding the minimum element. ans = min(ans, maxi -mini); return ans;#returning the final answer. # Driver Code # Given array arr[] arr = [ 1, 2, 3, 3, 2, 2 ]; N = len(arr); # Given subarray size Y = 4; # Function Call print(max_difference(arr, N, Y));
// function to calculate the Min difference //between maximum and minimum element //in all Y size subarrays function max_difference(arr, N, Y) { // variable to store Min difference //between maximum and minimum element/ let ans = Infinity; for (let i = 0; i <= N - Y; i++) { let maxi = -Infinity; let mini = Infinity; for (let j = i; j <= i + Y - 1; j++) { maxi = Math.max(maxi, arr[j]);// finding the maximum element. mini = Math.min(mini, arr[j]);// finding the minimum element. } ans = Math.min(ans, maxi - mini); } return ans;//returning the final answer. } // Driver Code // Given array arr[] let arr = [1, 2, 3, 3, 2, 2]; let N = arr.length; // Given subarray size let Y = 4; // Function Call console.log(max_difference(arr, N, Y)); using System; class Gfg { // function to calculate the Min difference // between maximum and minimum element // in all Y size subarrays static int max_difference(int[] arr, int N, int Y) { // variable to store Min difference // between maximum and minimum element int ans = int.MaxValue; for (int i = 0; i <= N - Y; i++) { int maxi = int.MinValue; int mini = int.MaxValue; for (int j = i; j <= i + Y - 1; j++) { maxi = Math.Max( maxi, arr[j]); // finding the maximum element. mini = Math.Min( mini, arr[j]); // finding the minimum element. } ans = Math.Min(ans, maxi - mini); } return ans; // returning the final answer. } // Driver Code static void Main(string[] args) { // Given array arr[] int[] arr = { 1, 2, 3, 3, 2, 2 }; int N = arr.Length; // Given subarray size int Y = 4; // Function Call Console.WriteLine(max_difference(arr, N, Y)); } } public class GFG { public static int maxDifference(int[] arr, int N, int Y) { // variable to store Min difference //between maximum and minimum element/ int ans = Integer.MAX_VALUE; for (int i = 0; i <= N - Y; i++) { int maxi = Integer.MIN_VALUE; int mini = Integer.MAX_VALUE; for (int j = i; j <= i + Y - 1; j++) { maxi = Math.max(maxi, arr[j]);// finding the maximum element. mini = Math.min(mini, arr[j]);// finding the minimum element. } ans = Math.min(ans, maxi - mini); } return ans;//returning the final answer. } public static void main(String[] args) { // Given array arr[] int[] arr = {1, 2, 3, 3, 2, 2}; int N = arr.length; // Given subarray size int Y = 4; // Function Call System.out.println(maxDifference(arr, N, Y)); } } Time Complexity: O(N*Y) where Y is the given subarray range and N is the size of the array.
Auxiliary Space: O(1)
Efficient Approach: The idea is to use the concept of the approach discussed in the Next Greater Element article. Below are the steps:
- Build two arrays maxarr[] and minarr[], where maxarr[] will store the index of the element which is next greater to the element at ith index and minarr[] will store the index of the next element which is less than the element at the ith index.
- Initialize a stack with 0 to store the indices in both the above cases.
- For each index, i in the range [0, N - Y], using a nested loop and sliding window approach form two arrays submax and submin. These arrays will store maximum and minimum elements in the subarray in ith iteration.
- Finally, calculate the minimum difference.
Below is the implementation of the above approach:
C++ // C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to get the maximum of all // the subarrays of size Y vector<int> get_submaxarr(int* arr, int n, int y) { int j = 0; stack<int> stk; // ith index of maxarr array // will be the index upto which // Arr[i] is maximum vector<int> maxarr(n); stk.push(0); for (int i = 1; i < n; i++) { // Stack is used to find the // next larger element and // keeps track of index of // current iteration while (stk.empty() == false and arr[i] > arr[stk.top()]) { maxarr[stk.top()] = i - 1; stk.pop(); } stk.push(i); } // Loop for remaining indexes while (!stk.empty()) { maxarr[stk.top()] = n - 1; stk.pop(); } vector<int> submax; for (int i = 0; i <= n - y; i++) { // j < i used to keep track // whether jth element is // inside or outside the window while (maxarr[j] < i + y - 1 or j < i) { j++; } submax.push_back(arr[j]); } // Return submax return submax; } // Function to get the minimum for // all subarrays of size Y vector<int> get_subminarr(int* arr, int n, int y) { int j = 0; stack<int> stk; // ith index of minarr array // will be the index upto which // Arr[i] is minimum vector<int> minarr(n); stk.push(0); for (int i = 1; i < n; i++) { // Stack is used to find the // next smaller element and // keeping track of index of // current iteration while (stk.empty() == false and arr[i] < arr[stk.top()]) { minarr[stk.top()] = i; stk.pop(); } stk.push(i); } // Loop for remaining indexes while (!stk.empty()) { minarr[stk.top()] = n; stk.pop(); } vector<int> submin; for (int i = 0; i <= n - y; i++) { // j < i used to keep track // whether jth element is inside // or outside the window while (minarr[j] <= i + y - 1 or j < i) { j++; } submin.push_back(arr[j]); } // Return submin return submin; } // Function to get minimum difference void getMinDifference(int Arr[], int N, int Y) { // Create submin and submax arrays vector<int> submin = get_subminarr(Arr, N, Y); vector<int> submax = get_submaxarr(Arr, N, Y); // Store initial difference int minn = submax[0] - submin[0]; int b = submax.size(); for (int i = 1; i < b; i++) { // Calculate temporary difference int dif = submax[i] - submin[i]; minn = min(minn, dif); } // Final minimum difference cout << minn << "\n"; } // Driver Code int main() { // Given array arr[] int arr[] = { 1, 2, 3, 3, 2, 2 }; int N = sizeof arr / sizeof arr[0]; // Given subarray size int Y = 4; // Function Call getMinDifference(arr, N, Y); return 0; } // Java program for the above approach import java.util.*; class GFG{ // Function to get the maximum of all // the subarrays of size Y static Vector<Integer> get_submaxarr(int[] arr, int n, int y) { int j = 0; Stack<Integer> stk = new Stack<Integer>(); // ith index of maxarr array // will be the index upto which // Arr[i] is maximum int[] maxarr = new int[n]; Arrays.fill(maxarr,0); stk.push(0); for(int i = 1; i < n; i++) { // Stack is used to find the // next larger element and // keeps track of index of // current iteration while (stk.size() != 0 && arr[i] > arr[stk.peek()]) { maxarr[stk.peek()] = i - 1; stk.pop(); } stk.push(i); } // Loop for remaining indexes while (stk.size() != 0) { maxarr[stk.size()] = n - 1; stk.pop(); } Vector<Integer> submax = new Vector<Integer>(); for(int i = 0; i <= n - y; i++) { // j < i used to keep track // whether jth element is // inside or outside the window while (maxarr[j] < i + y - 1 || j < i) { j++; } submax.add(arr[j]); } // Return submax return submax; } // Function to get the minimum for // all subarrays of size Y static Vector<Integer> get_subminarr(int[] arr, int n, int y) { int j = 0; Stack<Integer> stk = new Stack<Integer>(); // ith index of minarr array // will be the index upto which // Arr[i] is minimum int[] minarr = new int[n]; Arrays.fill(minarr,0); stk.push(0); for(int i = 1; i < n; i++) { // Stack is used to find the // next smaller element and // keeping track of index of // current iteration while (stk.size() != 0 && arr[i] < arr[stk.peek()]) { minarr[stk.peek()] = i; stk.pop(); } stk.push(i); } // Loop for remaining indexes while (stk.size() != 0) { minarr[stk.peek()] = n; stk.pop(); } Vector<Integer> submin = new Vector<Integer>(); for(int i = 0; i <= n - y; i++) { // j < i used to keep track // whether jth element is inside // or outside the window while (minarr[j] <= i + y - 1 || j < i) { j++; } submin.add(arr[j]); } // Return submin return submin; } // Function to get minimum difference static void getMinDifference(int[] Arr, int N, int Y) { // Create submin and submax arrays Vector<Integer> submin = get_subminarr(Arr, N, Y); Vector<Integer> submax = get_submaxarr(Arr, N, Y); // Store initial difference int minn = submax.get(0) - submin.get(0); int b = submax.size(); for(int i = 1; i < b; i++) { // Calculate temporary difference int dif = submax.get(i) - submin.get(i) + 1; minn = Math.min(minn, dif); } // Final minimum difference System.out.print(minn); } // Driver code public static void main(String[] args) { // Given array arr[] int[] arr = { 1, 2, 3, 3, 2, 2 }; int N = arr.length; // Given subarray size int Y = 4; // Function Call getMinDifference(arr, N, Y); } } // This code is contributed by decode2207 # Python3 program for the above approach # Function to get the maximum of all # the subarrays of size Y def get_submaxarr(arr, n, y): j = 0 stk = [] # ith index of maxarr array # will be the index upto which # Arr[i] is maximum maxarr = [0] * n stk.append(0) for i in range(1, n): # Stack is used to find the # next larger element and # keeps track of index of # current iteration while (len(stk) > 0 and arr[i] > arr[stk[-1]]): maxarr[stk[-1]] = i - 1 stk.pop() stk.append(i) # Loop for remaining indexes while (stk): maxarr[stk[-1]] = n - 1 stk.pop() submax = [] for i in range(n - y + 1): # j < i used to keep track # whether jth element is # inside or outside the window while (maxarr[j] < i + y - 1 or j < i): j += 1 submax.append(arr[j]) # Return submax return submax # Function to get the minimum for # all subarrays of size Y def get_subminarr(arr, n, y): j = 0 stk = [] # ith index of minarr array # will be the index upto which # Arr[i] is minimum minarr = [0] * n stk.append(0) for i in range(1 , n): # Stack is used to find the # next smaller element and # keeping track of index of # current iteration while (stk and arr[i] < arr[stk[-1]]): minarr[stk[-1]] = i stk.pop() stk.append(i) # Loop for remaining indexes while (stk): minarr[stk[-1]] = n stk.pop() submin = [] for i in range(n - y + 1): # j < i used to keep track # whether jth element is inside # or outside the window while (minarr[j] <= i + y - 1 or j < i): j += 1 submin.append(arr[j]) # Return submin return submin # Function to get minimum difference def getMinDifference(Arr, N, Y): # Create submin and submax arrays submin = get_subminarr(Arr, N, Y) submax = get_submaxarr(Arr, N, Y) # Store initial difference minn = submax[0] - submin[0] b = len(submax) for i in range(1, b): # Calculate temporary difference diff = submax[i] - submin[i] minn = min(minn, diff) # Final minimum difference print(minn) # Driver code # Given array arr[] arr = [ 1, 2, 3, 3, 2, 2 ] N = len(arr) # Given subarray size Y = 4 # Function call getMinDifference(arr, N, Y) # This code is contributed by Stuti Pathak
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Function to get the maximum of all // the subarrays of size Y static List<int> get_submaxarr(int[] arr, int n, int y) { int j = 0; Stack<int> stk = new Stack<int>(); // ith index of maxarr array // will be the index upto which // Arr[i] is maximum int[] maxarr = new int[n]; Array.Fill(maxarr,0); stk.Push(0); for (int i = 1; i < n; i++) { // Stack is used to find the // next larger element and // keeps track of index of // current iteration while (stk.Count!=0 && arr[i] > arr[stk.Peek()]) { maxarr[stk.Peek()] = i - 1; stk.Pop(); } stk.Push(i); } // Loop for remaining indexes while (stk.Count!=0) { maxarr[stk.Count] = n - 1; stk.Pop(); } List<int> submax = new List<int>(); for (int i = 0; i <= n - y; i++) { // j < i used to keep track // whether jth element is // inside or outside the window while (maxarr[j] < i + y - 1 || j < i) { j++; } submax.Add(arr[j]); } // Return submax return submax; } // Function to get the minimum for // all subarrays of size Y static List<int> get_subminarr(int[] arr, int n, int y) { int j = 0; Stack<int> stk = new Stack<int>(); // ith index of minarr array // will be the index upto which // Arr[i] is minimum int[] minarr = new int[n]; Array.Fill(minarr,0); stk.Push(0); for (int i = 1; i < n; i++) { // Stack is used to find the // next smaller element and // keeping track of index of // current iteration while (stk.Count!=0 && arr[i] < arr[stk.Peek()]) { minarr[stk.Peek()] = i; stk.Pop(); } stk.Push(i); } // Loop for remaining indexes while (stk.Count!=0) { minarr[stk.Peek()] = n; stk.Pop(); } List<int> submin = new List<int>(); for (int i = 0; i <= n - y; i++) { // j < i used to keep track // whether jth element is inside // or outside the window while (minarr[j] <= i + y - 1 || j < i) { j++; } submin.Add(arr[j]); } // Return submin return submin; } // Function to get minimum difference static void getMinDifference(int[] Arr, int N, int Y) { // Create submin and submax arrays List<int> submin = get_subminarr(Arr, N, Y); List<int> submax = get_submaxarr(Arr, N, Y); // Store initial difference int minn = submax[0] - submin[0]; int b = submax.Count; for (int i = 1; i < b; i++) { // Calculate temporary difference int dif = submax[i] - submin[i] + 1; minn = Math.Min(minn, dif); } // Final minimum difference Console.WriteLine(minn); } static void Main() { // Given array arr[] int[] arr = { 1, 2, 3, 3, 2, 2 }; int N = arr.Length; // Given subarray size int Y = 4; // Function Call getMinDifference(arr, N, Y); } } // This code is contributed by rameshtravel07. <script> // Javascript program for the above approach // Function to get the maximum of all // the subarrays of size Y function get_submaxarr(arr, n, y) { var j = 0; var stk = []; // ith index of maxarr array // will be the index upto which // Arr[i] is maximum var maxarr = Array(n); stk.push(0); for (var i = 1; i < n; i++) { // Stack is used to find the // next larger element and // keeps track of index of // current iteration while (stk.length!=0 && arr[i] > arr[stk[stk.length-1]]) { maxarr[stk[stk.length-1]] = i - 1; stk.pop(); } stk.push(i); } // Loop for remaining indexes while (stk.length!=0) { maxarr[stk[stk.length-1]] = n - 1; stk.pop(); } var submax = []; for (var i = 0; i <= n - y; i++) { // j < i used to keep track // whether jth element is // inside or outside the window while (maxarr[j] < i + y - 1 || j < i) { j++; } submax.push(arr[j]); } // Return submax return submax; } // Function to get the minimum for // all subarrays of size Y function get_subminarr(arr, n, y) { var j = 0; var stk = []; // ith index of minarr array // will be the index upto which // Arr[i] is minimum var minarr = Array(n); stk.push(0); for (var i = 1; i < n; i++) { // Stack is used to find the // next smaller element and // keeping track of index of // current iteration while (stk.length!=0 && arr[i] < arr[stk[stk.length-1]]) { minarr[stk[stk.length-1]] = i; stk.pop(); } stk.push(i); } // Loop for remaining indexes while (stk.length!=0) { minarr[stk[stk.length-1]] = n; stk.pop(); } var submin = []; for (var i = 0; i <= n - y; i++) { // j < i used to keep track // whether jth element is inside // or outside the window while (minarr[j] <= i + y - 1 || j < i) { j++; } submin.push(arr[j]); } // Return submin return submin; } // Function to get minimum difference function getMinDifference(Arr, N, Y) { // Create submin and submax arrays var submin = get_subminarr(Arr, N, Y); var submax = get_submaxarr(Arr, N, Y); // Store initial difference var minn = submax[0] - submin[0]; var b = submax.length; for (var i = 1; i < b; i++) { // Calculate temporary difference var dif = submax[i] - submin[i]; minn = Math.min(minn, dif); } // Final minimum difference document.write( minn + "<br>"); } // Driver Code // Given array arr[] var arr = [1, 2, 3, 3, 2, 2]; var N = arr.length // Given subarray size var Y = 4; // Function Call getMinDifference(arr, N, Y); </script> Time Complexity: O(N) where N is the size of the array.
Auxiliary Space: O(N) where N is the size of the array.
Related Topic: Subarrays, Subsequences, and Subsets in Array
Similar Reads
Minimize difference between maximum and minimum element of all possible subarrays Given an array arr[ ] of size N, the task is to find the minimum difference between maximum and minimum elements of all possible sized subarrays of arr[ ]. Examples: Input: arr[] = { 5, 14, 7, 10 } Output: 3Explanation: {7, 10} is the subarray having max element = 10 & min element = 7, and their
5 min read
Minimize difference between maximum and minimum array elements by removing a K-length subarray 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 = 2Output: 4Explanation: Remove the subarray {
10 min read
Split a given array into K subarrays minimizing the difference between their maximum and minimum Given a sorted array arr[] of N integers and an integer K, the task is to split the array into K subarrays such that the sum of the difference of maximum and minimum element of each subarray is minimized. Examples: Input: arr[] = {1, 3, 3, 7}, K = 4 Output: 0 Explanation: The given array can be spli
6 min read
Choose m elements having minimum difference between max and min Given an array arr[] of n integers. The task is to pick exactly m elements such that the maximum difference between any pair of these m elements in minimum.Examples:Input: arr[] = {7, 3, 2, 4, 9, 12, 56}, m = 3 Output: 2 Explanation: We pick {3, 2, 4}, we will get the minimum difference, that is 2.
5 min read
Minimum distance between the maximum and minimum element of a given Array Given an array A[] consisting of N elements, the task is to find the minimum distance between the minimum and the maximum element of the array.Examples: Input: arr[] = {3, 2, 1, 2, 1, 4, 5, 8, 6, 7, 8, 2} Output: 3 Explanation: The minimum element(= 1) is present at indices {2, 4} The maximum elemen
8 min read
Sum of minimum and maximum elements of all subarrays of size k. Given an array of both positive and negative integers, the task is to compute sum of minimum and maximum elements of all sub-array of size k.Examples: Input : arr[] = {2, 5, -1, 7, -3, -1, -2} K = 4Output : 18Explanation : Subarrays of size 4 are : {2, 5, -1, 7}, min + max = -1 + 7 = 6 {5, -1, 7, -3
15+ min read