Given an array arr[] of length N, the task is to find the maximum difference of integers in a subarray of size K.
Input: arr = [2, 3, -1, -5, 4, 0], K = 3
Output: 9
Explanation: Subarray [-1, -5, 4] contains the maximum difference between -5 and -4 as 9Input: arr = [-2, -4, 0, 1, 5, -6, 9], K =4
Output: 15
Explanation: Subarray [1, 5, -6, 9] contains the maximum difference between -6 and 9 as 15
Approach: The given problem can be solved using the two-pointers technique and the sliding window approach with TreeMap data structure. Below steps can be followed to solve the problem:
- Iterate the array arr till K – 1 and insert the elements in the TreeMap,
- If the integer is already present in the TreeMap, then increase its frequency by 1
- Iterate the array arr from K till the end of the array using a pointer right and at every iteration:
- Insert the element in the TreeMap, if it does not exist or else increase its frequency by 1
- Remove the leftmost element of the sliding window if its frequency is one, or else reduce its frequency by 1
- Calculate the difference between maximum and minimum elements by retrieving the first and last element from the treeMap, and also update the result res
- Return the result res
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the// maximum difference in integers// of subarray of size Kint maxDiffK( vector<int> arr, int K){ // Initialize length of the array int N = arr.size(); // Initialize a TreeMap map<int, int> tm; // Iterate the array arr till K - 1 for (int i = 0; i < K; i++) { // Get the frequency of the // arr[i] from the treemap int f = tm[arr[i]]; // If freq is null if (f == 0) { // Add the integer in the // treemap with frequency 1 tm[arr[i]] = 1; } else { // Increment the frequency // of the element tm[arr[i]] = f + 1; } } // Initialize MaxDiff to the absolute // Difference between greatest and // smallest element in the treemap int maxDiff = abs( tm.begin()->first - tm.rbegin()->first); // Iterate the array arr // from K till the end for (int i = K; i < N; i++) { // Get the frequency of the // current element from the treemap int f = tm[arr[i]]; // If freq is null then add the // integer in the treemap // with frequency 1 if (f == 0) { tm[arr[i]] = 1; } else { // Increment the frequency // of the element tm[arr[i]] = f + 1; } int freq = tm[arr[i - K]]; // If freq is 1 then remove the // value from the treemap if (freq == 1) tm.erase(tm.find(arr[i - K])); // Else reduce the frequency // of that element by 1 else tm[arr[i - K]] = freq - 1; // Update maxDiff with the maximum // of difference between smallest // and greatest element in treemap // and maxDiff maxDiff = max( maxDiff, abs( tm.begin()->first - tm.rbegin()->first)); } // Return the answer as maxDiff return maxDiff;}// Driver codeint main(){ // Initialize the array vector<int> arr = {2, 3, -1, -5, 4, 0}; // Initialize the value of K int K = 3; // Call the function and // print the result cout << (maxDiffK(arr, K)); return 0;}// This code is contributed by Potta Lokesh |
Java
// Java implementation for the above approachimport java.io.*;import java.util.*;class GFG { // Function to find the // maximum difference in integers // of subarray of size K public static int maxDiffK( int arr[], int K) { // Initialize length of the array int N = arr.length; // Initialize a TreeMap TreeMap<Integer, Integer> tm = new TreeMap<>(); // Iterate the array arr till K - 1 for (int i = 0; i < K; i++) { // Get the frequency of the // arr[i] from the treemap Integer f = tm.get(arr[i]); // If freq is null if (f == null) { // Add the integer in the // treemap with frequency 1 tm.put(arr[i], 1); } else { // Increment the frequency // of the element tm.put(arr[i], f + 1); } } // Initialize MaxDiff to the absolute // Difference between greatest and // smallest element in the treemap int maxDiff = Math.abs( tm.firstKey() - tm.lastKey()); // Iterate the array arr // from K till the end for (int i = K; i < N; i++) { // Get the frequency of the // current element from the treemap Integer f = tm.get(arr[i]); // If freq is null then add the // integer in the treemap // with frequency 1 if (f == null) { tm.put(arr[i], 1); } else { // Increment the frequency // of the element tm.put(arr[i], f + 1); } int freq = tm.get(arr[i - K]); // If freq is 1 then remove the // value from the treemap if (freq == 1) tm.remove(arr[i - K]); // Else reduce the frequency // of that element by 1 else tm.put(arr[i - K], freq - 1); // Update maxDiff with the maximum // of difference between smallest // and greatest element in treemap // and maxDiff maxDiff = Math.max( maxDiff, Math.abs( tm.firstKey() - tm.lastKey())); } // Return the answer as maxDiff return maxDiff; } // Driver code public static void main(String[] args) { // Initialize the array int[] arr = { 2, 3, -1, -5, 4, 0 }; // Initialize the value of K int K = 3; // Call the function and // print the result System.out.println(maxDiffK(arr, K)); }} |
Python3
# python code for the above approach# Function to find the# maximum difference in integers# of subarray of size Kdef maxDiffK(arr, K): # Initialize length of the array N = len(arr) # Initialize a TreeMap tm = {} # Iterate the array arr till K - 1 for i in range(0, K): # If freq is null if (not (arr[i] in tm)): # Add the integer in the # treemap with frequency 1 tm[arr[i]] = 1 else: # Increment the frequency # of the element tm[arr[i]] += 1 # Initialize MaxDiff to the absolute # Difference between greatest and # smallest element in the treemap maxDiff = max(list(tm)) - min(list(tm)) # Iterate the array arr # from K till the end for i in range(K, N): # If freq is null then add the # integer in the treemap # with frequency 1 if (not (arr[i] in tm)): tm[arr[i]] = 1 else: # Increment the frequency # of the element tm[arr[i]] += 1 freq = tm[arr[i - K]] # If freq is 1 then remove the # value from the treemap if (freq == 1): del tm[arr[i - K]] # Else reduce the frequency # of that element by 1 else: tm[arr[i - K]] -= 1 # Update maxDiff with the maximum # of difference between smallest # and greatest element in treemap # and maxDiff maxDiff = max(maxDiff, max(list(tm)) - min(list(tm))) # Return the answer as maxDiff return maxDiff# Driver codeif __name__ == "__main__": # Initialize the array arr = [2, 3, -1, -5, 4, 0] # Initialize the value of K K = 3 # Call the function and # print the result print(maxDiffK(arr, K)) # This code is contributed by rakeshsahni |
C#
// C# implementation for the above approachusing System;using System.Collections.Generic;using System.Linq;class GFG{ // Function to find the // maximum difference in ints // of subarray of size K public static int maxDiffK(int[] arr, int K) { // Initialize length of the array int N = arr.Length; // Initialize a TreeMap Dictionary<int, int> tm = new Dictionary<int, int>(); // Iterate the array arr till K - 1 for (int i = 0; i < K; i++) { // Get the frequency of the // arr[i] from the treemap if (!tm.ContainsKey(arr[i])) { // Add the int in the // treemap with frequency 1 tm[arr[i]] = 1; } else { // Increment the frequency // of the element tm[arr[i]] += 1; } } // Initialize MaxDiff to the absolute // Difference between greatest and // smallest element in the treemap int[] keys = tm.Keys.ToArray(); Array.Sort(keys); int maxDiff = Math.Abs(keys.First() - keys.Last()); // Iterate the array arr // from K till the end for (int i = K; i < N; i++) { // Get the frequency of the // current element from the treemap if (!tm.ContainsKey(arr[i])) { tm[arr[i]] = 1; } else { // Increment the frequency // of the element tm[arr[i]] += 1; } int freq = tm[arr[i - K]]; // If freq is 1 then remove the // value from the treemap if (freq == 1) tm.Remove(arr[i - K]); // Else reduce the frequency // of that element by 1 else tm[arr[i - K]] = freq - 1; // Update maxDiff with the maximum // of difference between smallest // and greatest element in treemap // and maxDiff keys = tm.Keys.ToArray(); Array.Sort(keys); maxDiff = Math.Max(maxDiff, Math.Abs(keys.First() - keys.Last())); } // Return the answer as maxDiff return maxDiff; } // Driver code public static void Main() { // Initialize the array int[] arr = { 2, 3, -1, -5, 4, 0 }; // Initialize the value of K int K = 3; // Call the function and // print the result Console.Write(maxDiffK(arr, K)); }}// This code is contributed by saurabh_jaiswal. |
Javascript
<script>// Javascript code for the above approach// Function to find the// maximum difference in integers// of subarray of size Kfunction maxDiffK(arr, K) { // Initialize length of the array let N = arr.length; // Initialize a TreeMap let tm = new Map(); // Iterate the array arr till K - 1 for (let i = 0; i < K; i++) { // Get the frequency of the // arr[i] from the treemap let f = tm.get(arr[i]); // If freq is null if (!f) { // Add the integer in the // treemap with frequency 1 tm.set(arr[i], 1); } else { // Increment the frequency // of the element tm.set(arr[i], f + 1); } } // Initialize MaxDiff to the absolute // Difference between greatest and // smallest element in the treemap let maxDiff = Math.abs([...tm.keys()].sort((a, b) => a - b)[0] - [...tm.keys()].sort((a, b) => b - a)[0]); // Iterate the array arr // from K till the end for (let i = K; i < N; i++) { // Get the frequency of the // current element from the treemap let f = tm.get(arr[i]); // If freq is null then add the // integer in the treemap // with frequency 1 if (!f) { tm.set(arr[i], 1); } else { // Increment the frequency // of the element tm.set(arr[i], f + 1); } let freq = tm.get(arr[i - K]); // If freq is 1 then remove the // value from the treemap if (freq == 1) tm.delete((arr[i - K])); // Else reduce the frequency // of that element by 1 else tm.set(arr[i - K], freq - 1); // Update maxDiff with the maximum // of difference between smallest // and greatest element in treemap // and maxDiff maxDiff = Math.max( maxDiff, Math.abs([...tm.keys()].sort((a, b) => a - b)[0] - [...tm.keys()].sort((a, b) => b - a)[0])); } // Return the answer as maxDiff return maxDiff;}// Driver code// Initialize the arraylet arr = [2, 3, -1, -5, 4, 0];// Initialize the value of Klet K = 3;// Call the function and// print the resultdocument.write((maxDiffK(arr, K)))// This code is contributed by Saurabh Jaiswal</script> |
Output
9
Time Complexity: O(N * log K)
Auxiliary Space: O(N)
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!