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
My Profile