Longest subarray with absolute difference between any pair at most X
Last Updated :
22 Sep, 2025
Given an integer array arr[] and an integer x, Find the longest sub-array where the absolute difference between any two elements is not greater than x.
Examples:
Input: arr[] = [8, 4, 5, 6, 7], x = 3
Output: [4, 5, 6, 7]
Explanation: The longest valid subarray is [4, 5, 6, 7] because max = 7, min = 4 → difference = 3 which is less than equal to x.
Input: arr[] = [1, 10, 12, 13, 14], x = 2
Output: [12, 13, 14]
Explanation: The longest valid subarray is [12, 13, 14] because max = 14, min = 12 → difference = 2 which is less than equal to x.
[Naive Approach] Checking all subarrays - O(n3) Time and O(1) Space
The idea is to consider all subarrays one by one, find the maximum and minimum element of that sub-array and check if their difference is not greater than x. Among all such sub-arrays print the longest sub-array.
C++
#include <iostream>
#include<vector>
#include<climits>
using namespace std;
vector<int> longestSubarray(vector<int>& arr, int x) {
int n = arr.size();
int start = 0, maxLen = 1;
for (int i=0; i<n; i++) {
for (int j=i; j<n; j++) {
// Find minimum and maximum elements
int mini = INT_MAX, maxi = INT_MIN;
for (int k=i; k<=j; k++) {
mini = min(mini, arr[k]);
maxi = max(maxi, arr[k]);
}
// If difference is less than x,
// compare length of subarray
if (maxi - mini <= x && maxLen < j-i+1) {
maxLen = j-i+1;
start = i;
}
}
}
vector<int> res;
for (int i = start; i < start+maxLen; i++) {
res.push_back(arr[i]);
}
return res;
}
int main() {
vector<int> arr = { 8, 4, 5, 6, 7 };
int x = 3;
vector<int> res = longestSubarray(arr, x);
for (auto val: res) {
cout << val << " ";
}
cout << endl;
return 0;
}
import java.util.ArrayList;
class GfG {
static ArrayList<Integer> longestSubarray(int[] arr, int x) {
int n = arr.length;
int start = 0, maxLen = 1;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
// Find minimum and maximum elements
int mini = Integer.MAX_VALUE, maxi = Integer.MIN_VALUE;
for (int k = i; k <= j; k++) {
mini = Math.min(mini, arr[k]);
maxi = Math.max(maxi, arr[k]);
}
// If difference is less than x,
// compare length of subarray
if (maxi - mini <= x && maxLen < j - i + 1) {
maxLen = j - i + 1;
start = i;
}
}
}
ArrayList<Integer> res = new ArrayList<>();
for (int i = start; i < start + maxLen; i++) {
res.add(arr[i]);
}
return res;
}
public static void main(String[] args) {
int[] arr = {8, 4, 5, 6, 7 };
int x = 3;
ArrayList<Integer> res = longestSubarray(arr, x);
for (int val : res) {
System.out.print(val + " ");
}
System.out.println();
}
}
def longestSubarray(arr, x):
n = len(arr)
start = 0
maxLen = 1
for i in range(n):
for j in range(i, n):
# Find minimum and maximum elements
mini = float('inf')
maxi = float('-inf')
for k in range(i, j + 1):
mini = min(mini, arr[k])
maxi = max(maxi, arr[k])
# If difference is less than x,
# compare length of subarray
if maxi - mini <= x and maxLen < j - i + 1:
maxLen = j - i + 1
start = i
return arr[start: start + maxLen]
if __name__ == "__main__":
arr = [8, 4, 5, 6, 7]
x = 3
res = longestSubarray(arr, x)
print(*res)
using System;
using System.Collections.Generic;
class GfG {
static List<int> longestSubarray(int[] arr, int x) {
int n = arr.Length;
int start = 0, maxLen = 1;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
// Find minimum and maximum elements
int mini = int.MaxValue, maxi = int.MinValue;
for (int k = i; k <= j; k++) {
mini = Math.Min(mini, arr[k]);
maxi = Math.Max(maxi, arr[k]);
}
// If difference is less than x,
// compare length of subarray
if (maxi - mini <= x && maxLen < j - i + 1) {
maxLen = j - i + 1;
start = i;
}
}
}
List<int> res = new List<int>();
for (int i = start; i < start + maxLen; i++) {
res.Add(arr[i]);
}
return res;
}
static void Main() {
int[] arr = {8, 4, 5, 6, 7};
int x = 3;
List<int> res = longestSubarray(arr, x);
Console.WriteLine(string.Join(" ", res));
}
}
function longestSubarray(arr, x) {
let n = arr.length;
let start = 0, maxLen = 1;
for (let i = 0; i < n; i++) {
for (let j = i; j < n; j++) {
// Find minimum and maximum elements
let mini = Infinity, maxi = -Infinity;
for (let k = i; k <= j; k++) {
mini = Math.min(mini, arr[k]);
maxi = Math.max(maxi, arr[k]);
}
// If difference is less than x,
// compare length of subarray
if (maxi - mini <= x && maxLen < j - i + 1) {
maxLen = j - i + 1;
start = i;
}
}
}
return arr.slice(start, start + maxLen);
}
// Driver Code
let arr = [8, 4, 5, 6, 7];
let x = 3;
let res = longestSubarray(arr, x);
console.log(res.join(" "));
[Better Approach] Using Sliding Window and Sorted Map - O(n * log n) Time and O(n) Space
We use a sliding window with an ordered map to maintain the minimum and maximum values in the current subarray. The window expands until the absolute difference exceeds x; if it does, we shrink the window from the left until the condition is satisfied again.
Working:
- Maintain two pointers start and end for the window.
- Insert elements into the map to track min and max.
- If (max - min) <= x, update the best subarray length.
- If (max - min) > x, move start forward and remove elements until valid.
- Finally, return the longest valid subarray found.
In C# and JavaScript, a custom structure is needed for min/max since they don’t have a built-in ordered map.
C++
#include <iostream>
#include <vector>
#include <map>
using namespace std;
vector<int> longestSubarray(vector<int>& arr, int x) {
int n = arr.size();
int maxLen = 0;
int beginning = 0;
map<int, int> window;
// Initialize the window
int start = 0, end = 0;
for (; end < n; end++) {
// Increment the count of that element in the window
window[arr[end]]++;
// maximum and minimum element in current window
auto minimum = window.begin()->first;
auto maximum = window.rbegin()->first;
// If the difference is not greater than X
if (maximum - minimum <= x) {
// Update the length of the longest subarray and
// store the beginning of the sub-array
if (maxLen < end - start + 1) {
maxLen = end - start + 1;
beginning = start;
}
}
// Decrease the size of the window
else {
while (start < end) {
// Remove the element at start
window[arr[start]]--;
// Remove the element from the window
// if its count is zero
if (window[arr[start]] == 0) {
window.erase(window.find(arr[start]));
}
// Increment the start of the window
start++;
// maximum and minimum element in the
// current window
auto minimum = window.begin()->first;
auto maximum = window.rbegin()->first;
// Stop decreasing the size of window
// when difference is not greater
if (maximum - minimum <= x)
break;
}
}
}
// Return the longest sub-array
vector<int> res;
for (int i = beginning; i < beginning + maxLen; i++)
res.push_back(arr[i]);
return res;
}
int main() {
vector<int> arr = {8, 4, 5, 6, 7 };
int x = 3;
vector<int> res = longestSubarray(arr, x);
for (auto val: res) {
cout << val << " ";
}
cout << endl;
return 0;
}
import java.util.ArrayList;
import java.util.TreeMap;
class GfG {
static ArrayList<Integer> longestSubarray(int[] arr, int x) {
int n = arr.length;
int maxLen = 0;
int beginning = 0;
// map to store the maximum and the minimum elements for
// a given window
TreeMap<Integer, Integer> window = new TreeMap<>();
int start = 0, end = 0;
for (; end < n; end++) {
// Increment the count of that element in the window
window.put(arr[end], window.getOrDefault(arr[end], 0) + 1);
// maximum and minimum element in current window
int minimum = window.firstKey();
int maximum = window.lastKey();
// If the difference is not greater than X
if (maximum - minimum <= x) {
// Update the length of the longest subarray and
// store the beginning of the sub-array
if (maxLen < end - start + 1) {
maxLen = end - start + 1;
beginning = start;
}
}
// Decrease the size of the window
else {
while (start < end) {
// Remove the element at start
window.put(arr[start], window.get(arr[start]) - 1);
// Remove the element from the window
// if its count is zero
if (window.get(arr[start]) == 0) {
window.remove(arr[start]);
}
// Increment the start of the window
start++;
// maximum and minimum element in the
// current window
minimum = window.firstKey();
maximum = window.lastKey();
// Stop decreasing the size of window
// when difference is not greater
if (maximum - minimum <= x)
break;
}
}
}
// Return the longest sub-array
ArrayList<Integer> res = new ArrayList<>();
for (int i = beginning; i < beginning + maxLen; i++)
res.add(arr[i]);
return res;
}
public static void main(String[] args) {
int[] arr = {8, 4, 5, 6, 7};
int x = 3;
ArrayList<Integer> res = longestSubarray(arr, x);
for (int val : res) {
System.out.print(val + " ");
}
System.out.println();
}
}
import bisect
def longestSubarray(arr, x):
n = len(arr)
window = []
max_len = 0
start = 0
beginning = 0
for end in range(n):
# insert arr[end] in sorted order
bisect.insort(window, arr[end])
# shrink window if max - min > x
while window[-1] - window[0] > x:
# remove arr[start] from window
idx = bisect.bisect_left(window, arr[start])
window.pop(idx)
start += 1
# update longest subarray
if end - start + 1 > max_len:
max_len = end - start + 1
beginning = start
return arr[beginning:beginning + max_len]
if __name__ == "__main__":
arr = [8, 4, 5, 6, 7]
x = 3
res = longestSubarray(arr, x)
for i in range(0, len(res)):
print(res[i], end=" ")
using System;
using System.Collections.Generic;
using System.Linq;
// Custom multiset with O(1) min/max tracking
class MultiSet {
private SortedDictionary<int, int> dict = new SortedDictionary<int, int>();
private int minVal = int.MaxValue;
private int maxVal = int.MinValue;
// Insert element into multiset
public void Add(int x) {
if (!dict.ContainsKey(x)) dict[x] = 0;
dict[x]++;
if (x < minVal) minVal = x;
if (x > maxVal) maxVal = x;
}
// Remove element from multiset
public void Remove(int x) {
if (!dict.ContainsKey(x)) return;
dict[x]--;
if (dict[x] == 0) dict.Remove(x);
// Update min/max if the removed element was min or max
if (x == minVal || x == maxVal) {
if (dict.Count == 0) {
minVal = int.MaxValue;
maxVal = int.MinValue;
} else {
minVal = GetFirstKey();
maxVal = GetLastKey();
}
}
}
// Get smallest key in dictionary
private int GetFirstKey() {
foreach (var kv in dict) return kv.Key;
return 0;
}
// Get largest key in dictionary
private int GetLastKey() {
using (var e = dict.GetEnumerator()) {
int last = 0;
while (e.MoveNext()) last = e.Current.Key;
return last;
}
}
public int Min() => minVal;
public int Max() => maxVal;
}
class GfG {
static List<int> longestSubarray(int[] arr, int x) {
int n = arr.Length;
int maxLen = 0, beginning = 0;
MultiSet window = new MultiSet();
int start = 0;
// Expand the window
for (int end = 0; end < n; end++) {
window.Add(arr[end]);
// Shrink while condition is violated
while (window.Max() - window.Min() > x) {
window.Remove(arr[start]);
start++;
}
// Update best window length
if (end - start + 1 > maxLen) {
maxLen = end - start + 1;
beginning = start;
}
}
// Build result subarray
List<int> res = new List<int>();
for (int i = beginning; i < beginning + maxLen; i++)
res.Add(arr[i]);
return res;
}
static void Main() {
int[] arr = { 8, 4, 5, 6, 7 };
int x = 3;
List<int> res = longestSubarray(arr, x);
Console.WriteLine(string.Join(" ", res));
}
}
class Heap {
constructor(compare) {
this.data = [];
this.compare = compare;
}
size() { return this.data.length; }
peek() { return this.data[0]; }
push(val) {
this.data.push(val);
this._siftUp(this.data.length - 1);
}
pop() {
if (this.size() === 0) return null;
const top = this.data[0];
const last = this.data.pop();
if (this.size() > 0) {
this.data[0] = last;
this._siftDown(0);
}
return top;
}
_siftUp(i) {
while (i > 0) {
const p = (i - 1) >> 1;
if (this.compare(this.data[i], this.data[p])) {
[this.data[i], this.data[p]] = [this.data[p], this.data[i]];
i = p;
} else break;
}
}
_siftDown(i) {
const n = this.size();
while (true) {
let l = i * 2 + 1, r = i * 2 + 2, best = i;
if (l < n && this.compare(this.data[l], this.data[best])) best = l;
if (r < n && this.compare(this.data[r], this.data[best])) best = r;
if (best !== i) {
[this.data[i], this.data[best]] = [this.data[best], this.data[i]];
i = best;
} else break;
}
}
}
function longestSubarray(arr, x) {
const n = arr.length;
let maxLen = 0, beginning = 0;
// frequency map
const freq = new Map();
// min-heap and max-heap
const minHeap = new Heap((a, b) => a < b);
const maxHeap = new Heap((a, b) => a > b);
let start = 0;
for (let end = 0; end < n; end++) {
freq.set(arr[end], (freq.get(arr[end]) || 0) + 1);
minHeap.push(arr[end]);
maxHeap.push(arr[end]);
// shrink window while invalid
while (true) {
while (minHeap.size() > 0 && (freq.get(minHeap.peek()) || 0) === 0)
minHeap.pop();
while (maxHeap.size() > 0 && (freq.get(maxHeap.peek()) || 0) === 0)
maxHeap.pop();
if (maxHeap.peek() - minHeap.peek() <= x) break;
freq.set(arr[start], freq.get(arr[start]) - 1);
start++;
}
// update longest window
if (end - start + 1 > maxLen) {
maxLen = end - start + 1;
beginning = start;
}
}
let res = [];
for (let i = beginning; i < beginning + maxLen; i++) res.push(arr[i]);
return res;
}
// Driver Code
let arr = [8, 4, 5, 6, 7];
let x = 3;
let res = longestSubarray(arr, x);
console.log(res.join(" "));
[Expected Approach] Using Dequeues - O(n) Time and O(n) Space
We will be using two deques to maintain the minimum and maximum of the current window in O(1). Expand the window while the difference ≤ x, and shrink it when the difference > x to find the longest valid subarray.
Working:
- Keep two deques:
-> minDeque → increasing order (front = minimum).
-> maxDeque → decreasing order (front = maximum). - Traverse array with end pointer:
-> Insert element in both deques while maintaining order. - If (maxDeque.front() - minDeque.front()) > x:
-> Move start pointer forward.
-> Remove elements from deques if they go out of the window. - Track the maximum window size where difference ≤ x.
C++
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
vector<int> longestSubarray(vector<int>& arr, int x) {
deque<int> minQueue, maxQueue;
int n = arr.size(), start = 0, end = 0;
// Pointers to mark the range of maximum subarray
int resStart = 0, resEnd = 0;
while (end < n) {
// Pop the elements greater than current element
// from min Queue
while (!minQueue.empty()
&& arr[minQueue.back()] > arr[end])
minQueue.pop_back();
// Pop the elements smaller than current element
// from max Queue
while (!maxQueue.empty()
&& arr[maxQueue.back()] < arr[end])
maxQueue.pop_back();
minQueue.push_back(end);
maxQueue.push_back(end);
// Check if the subarray has maximum difference less
// than x
while (arr[maxQueue.front()] - arr[minQueue.front()]
> x) {
// Reduce the length of sliding window by moving
// the start pointer
if (start == minQueue.front())
minQueue.pop_front();
if (start == maxQueue.front())
maxQueue.pop_front();
start += 1;
}
// Maximize the subarray length
if (end - start > resEnd - resStart) {
resStart = start;
resEnd = end;
}
end += 1;
}
vector<int> res;
for (int i = resStart; i <= resEnd; i++)
res.push_back(arr[i]);
return res;
}
int main() {
vector<int> arr = { 8, 4, 5, 6, 7 };
int x = 3;
vector<int> res = longestSubarray(arr, x);
for (auto val: res) {
cout << val << " ";
}
cout << endl;
return 0;
}
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
class GfG {
static ArrayList<Integer> longestSubarray(int[] arr, int x) {
Deque<Integer> minQueue = new LinkedList<>();
Deque<Integer> maxQueue = new LinkedList<>();
int n = arr.length, start = 0, end = 0;
int resStart = 0, resEnd = 0;
while (end < n) {
// Pop the elements greater than current element
// from min Queue
while (!minQueue.isEmpty() && arr[minQueue.peekLast()] > arr[end])
minQueue.pollLast();
// Pop the elements smaller than current element
// from max Queue
while (!maxQueue.isEmpty() && arr[maxQueue.peekLast()] < arr[end])
maxQueue.pollLast();
// Push the current index to both the queues
minQueue.addLast(end);
maxQueue.addLast(end);
// Check if the subarray has maximum difference less
// than x
while (arr[maxQueue.peekFirst()] - arr[minQueue.peekFirst()] > x) {
// Reduce the length of sliding window by moving
// the start pointer
if (start == minQueue.peekFirst())
minQueue.pollFirst();
if (start == maxQueue.peekFirst())
maxQueue.pollFirst();
start += 1;
}
// Maximize the subarray length
if (end - start > resEnd - resStart) {
resStart = start;
resEnd = end;
}
end += 1;
}
ArrayList<Integer> res = new ArrayList<>();
for (int i = resStart; i <= resEnd; i++)
res.add(arr[i]);
return res;
}
public static void main(String[] args) {
int[] arr = { 8, 4, 5, 6, 7 };
int x = 3;
ArrayList<Integer> res = longestSubarray(arr, x);
for (int val : res) {
System.out.print(val + " ");
}
System.out.println();
}
}
from collections import deque
def longestSubarray(arr, x):
minQueue = deque()
maxQueue = deque()
n = len(arr)
start = end = 0
resStart = resEnd = 0
while end < n:
# Pop the elements greater than current element
# from min Queue
while minQueue and arr[minQueue[-1]] > arr[end]:
minQueue.pop()
# Pop the elements smaller than current element
# from max Queue
while maxQueue and arr[maxQueue[-1]] < arr[end]:
maxQueue.pop()
# Push the current index to both the queues
minQueue.append(end)
maxQueue.append(end)
# Check if the subarray has maximum difference less
# than x
while arr[maxQueue[0]] - arr[minQueue[0]] > x:
# Reduce the length of sliding window by moving
# the start pointer
if start == minQueue[0]:
minQueue.popleft()
if start == maxQueue[0]:
maxQueue.popleft()
start += 1
# Maximize the subarray length
if end - start > resEnd - resStart:
resStart, resEnd = start, end
end += 1
return arr[resStart:resEnd+1]
if __name__ == "__main__":
arr = [8, 4, 5, 6, 7]
x = 3
res = longestSubarray(arr, x)
print(*res)
using System;
using System.Collections.Generic;
class GfG {
static List<int> longestSubarray(int[] arr, int x) {
LinkedList<int> minQueue = new LinkedList<int>();
LinkedList<int> maxQueue = new LinkedList<int>();
int n = arr.Length, start = 0, end = 0;
int resStart = 0, resEnd = 0;
while (end < n) {
// Pop the elements greater than current element
// from min Queue
while (minQueue.Count > 0 && arr[minQueue.Last.Value] > arr[end])
minQueue.RemoveLast();
// Pop the elements smaller than current element
// from max Queue
while (maxQueue.Count > 0 && arr[maxQueue.Last.Value] < arr[end])
maxQueue.RemoveLast();
// Push the current index to both the queues
minQueue.AddLast(end);
maxQueue.AddLast(end);
// Check if the subarray has maximum difference less
// than x
while (arr[maxQueue.First.Value] - arr[minQueue.First.Value] > x) {
// Reduce the length of sliding window by moving
// the start pointer
if (start == minQueue.First.Value)
minQueue.RemoveFirst();
if (start == maxQueue.First.Value)
maxQueue.RemoveFirst();
start += 1;
}
// Maximize the subarray length
if (end - start > resEnd - resStart) {
resStart = start;
resEnd = end;
}
end += 1;
}
// Return the longest sub-array
List<int> res = new List<int>();
for (int i = resStart; i <= resEnd; i++)
res.Add(arr[i]);
return res;
}
static void Main() {
int[] arr = { 8, 4, 5, 6, 7 };
int x = 3;
List<int> res = longestSubarray(arr, x);
Console.WriteLine(string.Join(" ", res));
}
}
function longestSubarray(arr, x) {
let minQueue = [];
let maxQueue = [];
let start = 0, end = 0, resStart = 0, resEnd = 0;
while (end < arr.length) {
// Maintain minQueue: remove elements greater than current
while (minQueue.length && arr[minQueue[minQueue.length - 1]] > arr[end])
minQueue.pop();
// Maintain maxQueue: remove elements smaller than current
while (maxQueue.length && arr[maxQueue[maxQueue.length - 1]] < arr[end])
maxQueue.pop();
minQueue.push(end);
maxQueue.push(end);
// Shrink window if difference exceeds x
while (arr[maxQueue[0]] - arr[minQueue[0]] > x) {
if (start === minQueue[0]) minQueue.shift();
if (start === maxQueue[0]) maxQueue.shift();
start++;
}
// Update result if current window is longer
if (end - start > resEnd - resStart) {
resStart = start;
resEnd = end;
}
end++;
}
// Return the longest subarray satisfying the condition
return arr.slice(resStart, resEnd + 1);
}
// Driver Code
let arr = [8, 4, 5, 6, 7];
let x = 3;
const res = longestSubarray(arr, x);
console.log(res.join(" "));
Explore
DSA Fundamentals
Data Structures
Algorithms
Advanced
Interview Preparation
Practice Problem