|
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++
#include <bits/stdc++.h>
using namespace std;
int findMaximumDifference(vector<int>& arr, int K)
{
int max_diff = INT_MIN;
for (int i = 0; i < arr.size() - K; i++) {
int diff = abs(arr[i] - arr[i + K]);
max_diff = max(diff, max_diff);
}
return max_diff;
}
int main()
{
vector<int> arr = { 2, 9, 7, 4, 6, 8, 3 };
int K = 2;
cout << findMaximumDifference(arr, K) << endl;
return 0;
}
|
Java
import java.util.ArrayList;
import java.util.List;
public class Main {
static int findMaximumDifference(List<Integer> arr, int K) {
int max_diff = Integer.MIN_VALUE;
for (int i = 0; i < arr.size() - K; i++) {
int diff = Math.abs(arr.get(i) - arr.get(i + K));
max_diff = Math.max(diff, max_diff);
}
return max_diff;
}
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;
System.out.println(findMaximumDifference(arr, K));
}
}
|
Python3
def find_maximum_difference(arr, K):
max_diff = float('-inf')
for i in range(len(arr) - K):
diff = abs(arr[i] - arr[i + K])
max_diff = max(diff, max_diff)
return max_diff
arr = [2, 9, 7, 4, 6, 8, 3]
K = 2
print(find_maximum_difference(arr, K))
|
C#
using System;
using System.Collections.Generic;
class MainClass
{
static int FindMaximumDifference(List<int> arr, int K)
{
int max_diff = int.MinValue;
for (int i = 0; i < arr.Count - K; i++)
{
int diff = Math.Abs(arr[i] - arr[i + K]);
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;
Console.WriteLine(FindMaximumDifference(arr, K));
}
}
|
Javascript
function findMaximumDifference(arr, K) {
let max_diff = Number.MIN_VALUE;
for (let i = 0; i < arr.length - K; i++) {
let diff = Math.abs(arr[i] - arr[i + K]);
max_diff = Math.max(diff, max_diff);
}
return max_diff;
}
let arr = [2, 9, 7, 4, 6, 8, 3];
let K = 2;
console.log(findMaximumDifference(arr, K));
|
Time Complexity: O(N), where N is the number of elements in the array arr[]
Auxiliary Space: O(1)
|
