Find maximum difference between elements having a fixed index difference of K

Last Updated : 16 Nov, 2023

Given an integer K and an unsorted array of integers arr[], find the maximum difference between elements in the array having a fixed index difference of K.

Examples:

Input: arr[] = [2, 9, 7, 4, 6, 8, 3], K = 2
Output: 5
Explanation: The maximum absolute difference with an index difference of two is 5, which occurs between arr[0] and arr[2]

Input: arr[] = [5, 1, 9, 3, 7, 8, 2, 4], K = 3
Output: 6
Explanation: The maximum absolute difference with an index difference of three is 6, which occurs between arr[1] and arr[4]

Approach: The problem can be solved using the following approach:

Iterate through the array, keeping track of the absolute current difference and the maximum difference encountered so far. If the absolute current difference is greater than maximum difference, then update the maximum difference.

Steps to solve the problem:

Initialize a variable max_diff to track the maximum difference and set it to a very small value initially.
Iterate through the array from the beginning to the (last - K)^th element
- For each index, i, calculate the absolute difference between (arr[i] - arr[i + k]).
- Compare the calculated difference with the current max_diff. If the calculated difference is greater than max_diff, update max_diff with the new value.
After the iteration, max_diff will contain the maximum difference between elements with a K-index difference.
Return max_diff

Below is the implementation of the approach:

C++

// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Function to find the maximum difference with // a K-index difference in an array int findMaximumDifference(vector<int>& arr, int K) {  // Initialize the maximum difference  // to a very small value  int max_diff = INT_MIN;  // Iterate through the array with a step  // of K to compare the elements  for (int i = 0; i < arr.size() - K; i++) {  // Calculate the difference  // between elements  int diff = abs(arr[i] - arr[i + K]);  // Update max_diff if a larger  // difference is found  max_diff = max(diff, max_diff);  }  return max_diff; } // Driver code int main() {  vector<int> arr = { 2, 9, 7, 4, 6, 8, 3 };  int K = 2;  // Find the maximum difference  cout << findMaximumDifference(arr, K) << endl;  return 0; }

Java

import java.util.ArrayList; import java.util.List; public class Main {  // Function to find the maximum difference with  // a K-index difference in an array  static int findMaximumDifference(List<Integer> arr, int K) {  // Initialize the maximum difference  // to a very small value  int max_diff = Integer.MIN_VALUE;  // Iterate through the array with a step  // of K to compare the elements  for (int i = 0; i < arr.size() - K; i++) {  // Calculate the difference between elements  int diff = Math.abs(arr.get(i) - arr.get(i + K));  // Update max_diff if a larger difference is found  max_diff = Math.max(diff, max_diff);  }  return max_diff;  }  // Driver code  public static void main(String[] args) {  List<Integer> arr = new ArrayList<>();  arr.add(2);  arr.add(9);  arr.add(7);  arr.add(4);  arr.add(6);  arr.add(8);  arr.add(3);  int K = 2;  // Find the maximum difference  System.out.println(findMaximumDifference(arr, K));  } }

Python3

def find_maximum_difference(arr, K): # Initialize the maximum difference to a very small value max_diff = float('-inf') # Iterate through the list with a step of K to compare the elements for i in range(len(arr) - K): # Calculate the difference between elements diff = abs(arr[i] - arr[i + K]) # Update max_diff if a larger difference is found max_diff = max(diff, max_diff) return max_diff # Driver code arr = [2, 9, 7, 4, 6, 8, 3] K = 2 # Find the maximum difference print(find_maximum_difference(arr, K))

using System; using System.Collections.Generic; class MainClass {  // Function to find the maximum difference with  // a K-index difference in a list  static int FindMaximumDifference(List<int> arr, int K)  {  // Initialize the maximum difference  // to a very small value  int max_diff = int.MinValue;  // Iterate through the list with a step  // of K to compare the elements  for (int i = 0; i < arr.Count - K; i++)  {  // Calculate the difference between elements  int diff = Math.Abs(arr[i] - arr[i + K]);  // Update max_diff if a larger difference is found  max_diff = Math.Max(diff, max_diff);  }  return max_diff;  }  public static void Main(string[] args)  {  List<int> arr = new List<int>  {  2, 9, 7, 4, 6, 8, 3  };  int K = 2;  // Find the maximum difference  Console.WriteLine(FindMaximumDifference(arr, K));  } }

JavaScript

// Javascript code for the above approach // Function to find the maximum difference with // a K-index difference in an array function findMaximumDifference(arr, K) {  // Initialize the maximum difference  // to a very small value  let max_diff = Number.MIN_VALUE;  // Iterate through the array with a step  // of K to compare the elements  for (let i = 0; i < arr.length - K; i++) {  // Calculate the difference between elements  let diff = Math.abs(arr[i] - arr[i + K]);  // Update max_diff if a larger difference is found  max_diff = Math.max(diff, max_diff);  }  return max_diff; } // Driver code let arr = [2, 9, 7, 4, 6, 8, 3]; let K = 2; // Find the maximum difference console.log(findMaximumDifference(arr, K)); // This code is contributed by ragul21