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 subarraysint 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 Codeint 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;} |
Python3
import sys# function to calculate the Min difference #between maximum and minimum element#in all Y size subarraysdef 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 sizeY = 4;# Function Callprint(max_difference(arr, N, Y)); |
Javascript
// function to calculate the Min difference //between maximum and minimum element//in all Y size subarraysfunction 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 sizelet Y = 4;// Function Callconsole.log(max_difference(arr, N, Y)); |
C#
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)); }} |
Java
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)); }} |
Output
1
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
// Java program for the above approachimport java.util.*;class GFG{// Function to get the maximum of all// the subarrays of size Ystatic 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 Ystatic 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 differencestatic 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 codepublic 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
# 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 sizeY = 4# Function callgetMinDifference(arr, N, Y) # This code is contributed by Stuti Pathak |
C#
// C# program for the above approachusing 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. |
Javascript
<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> |
Output:
1
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
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
