Closest Difference Pair — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Two Pointers and solve the Closest Difference Pair problem optimally.
O(n)O(1)Problem Description
You are given a sorted array of integers nums in non-decreasing order and an integer target. Your task is to find two distinct indices i and j such that i < j, which minimizes the absolute difference between the value nums[j] - nums[i] and the target. Specifically, you must minimize the quantity |(nums[j] - nums[i]) - target|.
Return the minimum possible value of this absolute difference. If multiple pairs yield the same minimum difference, return that minimum value.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Closest Difference Pair"
WHY DOES IT MATTER?
The two‑pointer pattern transforms a potentially exponential pairwise comparison into a linear walk by leveraging sorted order. It is a cornerstone technique for range‑based, sum‑or‑difference, and window‑size problems, making it indispensable for high‑throughput interview coding.
OPTIMIZATION CHALLENGE
The key insight is recognizing that nums[j] - nums[i] is a monotonic function of j for a fixed i. This allows us to decide deterministically which pointer to move based solely on the sign of (currentGap - target), eliminating the need for exhaustive pair checks.
REAL-WORLD CONNECTION
Think of a load balancer monitoring latency differences between two servers. As traffic patterns shift, the balancer slides a window over sorted latency logs, adjusting pointers to keep the latency gap as close as possible to a target SLA, analogous to the algorithm's pointer adjustments.
During an interview, write the two‑pointer skeleton first, then immediately add the absolute‑difference update inside the loop. Keep the loop condition simple (while left < right) and avoid extra nested loops; this signals to the interviewer that you understand both correctness and optimality.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem asks for two indices i < j in a non‑decreasing sorted array such that the absolute difference between the pairwise gap nums[j] - nums[i] and a given target is minimized. A naive double‑loop enumerates every possible pair, yielding O(n²) time, which quickly becomes infeasible for n up to 10⁵ or higher. Because the array is sorted, the difference nums[j] - nums[i] is monotonic with respect to moving the right pointer j forward while keeping i fixed, and likewise decreasing when i moves forward. This monotonicity enables the two‑pointer technique: start with i at the beginning and j just ahead, then adjust pointers based on whether the current gap is larger or smaller than the target, always moving the pointer that can bring the gap closer to the target. The optimal paradigm therefore combines sorted‑array properties with a linear scan, reducing the search space from quadratic to linear while preserving correctness.
In practice, the two‑pointer approach works because for any fixed i, the function f(j) = (nums[j] - nums[i]) - target is strictly increasing as j increases. If f(j) is positive (gap too large), moving i forward can only decrease the gap, while if f(j) is negative (gap too small), moving j forward can increase it. By iteratively tightening the window, we guarantee that every candidate pair is examined at most once, achieving O(n) time and O(1) extra space. This pattern is a classic example of exploiting order to transform a combinatorial search into a deterministic walk.
Interview Questions on This Problem
Q1How would you adapt the two‑pointer solution if the array were not sorted?
If the array is unsorted, first sort a copy of the array (O(n log n)) and keep track of original indices via a pair of (value, index). Then apply the same two‑pointer scan on the sorted values, returning the original indices of the best pair. The overall complexity becomes O(n log n) time and O(n) space.
Q2Can you extend this algorithm to find the k pairs whose differences are closest to the target?
Yes. Use a min‑heap to store candidate pairs generated by moving pointers from each start position. Initially push (i, i+1) for all i. Pop the smallest absolute difference, record the pair, then push the next pair (i, j+1) if j+1 < n. This yields O(k log n) additional time after the initial O(n) scan, while maintaining O(n) space for the heap.
Q3Why does the two‑pointer technique guarantee the global optimum for this problem?
Because the sorted order makes the gap function monotonic in each pointer direction. At any step, moving the left pointer can only reduce an overshoot, and moving the right pointer can only increase an undershoot. This property ensures that no better pair is skipped, and the algorithm explores all feasible transitions that could improve the current best absolute difference.
Examples
Input
nums = [1, 3, 5, 7, 9], target = 4
Output
0
Explanation: We examine pairs to find the difference closest to 4. The pair (1, 5) at indices (0, 2) gives a difference of 5 - 1 = 4. The absolute deviation is |4 - 4| = 0. Since 0 is the minimum possible absolute difference, the answer is 0.
Input
nums = [2, 4, 6, 8], target = 5
Output
0
Explanation: Possible differences are: 4-2=2 (|2-5|=3), 6-2=4 (|4-5|=1), 8-2=6 (|6-5|=1), 6-4=2 (|2-5|=3), 8-4=4 (|4-5|=1), 8-6=2 (|2-5|=3). The minimum absolute deviation is 1, achieved by pairs (2,6) and (4,8).
Input
nums = [1, 10, 20, 30], target = 15
Output
1
Explanation: Differences: 10-1=9 (|9-15|=6), 20-1=19 (|19-15|=4), 30-1=29 (|29-15|=14), 20-10=10 (|10-15|=5), 30-10=20 (|20-15|=5), 30-20=10 (|10-15|=5). The minimum absolute deviation is 4, from the pair (1, 20).
Input
nums = [5, 5, 5, 5], target = 0
Output
0
Explanation: Any pair of indices (i, j) with i < j yields nums[j] - nums[i] = 5 - 5 = 0. The absolute deviation is |0 - 0| = 0. Thus, the minimum value is 0.
Constraints
- 2 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- -10^9 <= target <= 10^9
- nums is sorted in non-decreasing order
Optimal Approach & Strategy
Use two pointers on the sorted array, moving the left pointer when the gap exceeds the target and the right pointer otherwise, updating the best absolute difference on each step. This yields O(n) time and O(1) extra space.
Brute Force Approach
Enumerate every i < j pair, compute |(nums[j]-nums[i]) - target|, and keep the minimum. This requires O(n²) time.
Code Solutions
function closestDifferencePair(nums, target) {
let n = nums.length;
let left = 0, right = 1;
let bestIdx = 0;
let bestDiff = Number.MAX_SAFE_INTEGER;
while (left < n && right < n) {
if (left === right) {
right++;
continue;
}
let curDiff = nums[right] - nums[left];
let absDiff = Math.abs(curDiff - target);
if (absDiff < bestDiff) {
bestDiff = absDiff;
bestIdx = left;
}
if (curDiff < target) {
left++;
} else if (curDiff > target) {
right++;
} else {
return left;
}
}
return bestIdx;
}int closestDifferencePair(const vector<int>& nums, int target) {
int n = nums.size();
int left = 0, right = 1;
int bestIdx = 0;
int bestDiff = INT_MAX;
while (left < n && right < n) {
if (left == right) {
++right;
continue;
}
int curDiff = nums[right] - nums[left];
int absDiff = abs(curDiff - target);
if (absDiff < bestDiff) {
bestDiff = absDiff;
bestIdx = left;
}
if (curDiff < target) {
++left;
} else if (curDiff > target) {
++right;
} else {
// exact match
return left;
}
}
return bestIdx;
}public int closestDifferencePair(int[] nums, int target) {
int n = nums.length;
int left = 0, right = 1;
int bestIdx = 0;
int bestDiff = Integer.MAX_VALUE;
while (left < n && right < n) {
if (left == right) {
right++;
continue;
}
int curDiff = nums[right] - nums[left];
int absDiff = Math.abs(curDiff - target);
if (absDiff < bestDiff) {
bestDiff = absDiff;
bestIdx = left;
}
if (curDiff < target) {
left++;
} else if (curDiff > target) {
right++;
} else {
return left;
}
}
return bestIdx;
}def closest_difference_pair(nums, target):
n = len(nums)
left, right = 0, 1
best_idx = 0
best_diff = float('inf')
while left < n and right < n:
if left == right:
right += 1
continue
cur_diff = nums[right] - nums[left]
abs_diff = abs(cur_diff - target)
if abs_diff < best_diff:
best_diff = abs_diff
best_idx = left
if cur_diff < target:
left += 1
elif cur_diff > target:
right += 1
else:
return left
return best_idxfunction closestDifferencePair(nums, target) {
let n = nums.length;
let left = 0, right = 1;
let bestIdx = 0;
let bestDiff = Number.MAX_SAFE_INTEGER;
while (left < n && right < n) {
if (left === right) {
right++;
continue;
}
let curDiff = nums[right] - nums[left];
let absDiff = Math.abs(curDiff - target);
if (absDiff < bestDiff) {
bestDiff = absDiff;
bestIdx = left;
}
if (curDiff < target) {
left++;
} else if (curDiff > target) {
right++;
} else {
return left;
}
}
return bestIdx;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.