Closest Difference Pair — Problem Statement & Solution Guide
Problem Description
Given a 0-indexed sorted integer array nums and a target integer target, find a pair of indices (i, j) such that i < j and the absolute difference between their value difference and the target, given by |(nums[j] - nums[i]) - target|, is minimized. Return this minimum possible absolute difference.
Examples
Input
[1, 2, 3, 4, 5], 3
Output
1
Explanation: Step-by-step: with input [1, 2, 3, 4, 5] and target 3, we find the pair (1, 2) with a difference of 1, which is less than the target. The pair (2, 3) has a difference of 1, which is also less than the target. The pair (3, 4) has a difference of 1, which is also less than the target. The pair (4, 5) has a difference of 1, which is also less than the target. The minimum absolute difference is 1, which is obtained by the pairs (1, 2), (2, 3), (3, 4), or (4, 5) with a difference of 1.
Input
[1, 5, 10, 20], 6
Output
3
Explanation: Step-by-step: with input [1, 5, 10, 20] and target 6, we find the pair (1, 5) with a difference of 4, which is less than the target. The pair (5, 10) has a difference of 5, which is also less than the target. The pair (1, 10) has a difference of 9, and the absolute difference between this pair difference and the target is 3. The pair (5, 20) has a difference of 15, and the absolute difference between this pair difference and the target is 9. The pair (1, 20) has a difference of 19, and the absolute difference between this pair difference and the target is 13. The minimum absolute difference is 3, which is obtained by the pair (1, 10) with a difference of 9.
Constraints
- 2 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- nums is sorted in non-decreasing order.
- 0 <= target <= 10^9
Optimal Approach & Strategy
Using a two-pointer approach, we initialize two pointers, i at 0 and j at 1. Since the array is sorted, if the current difference nums[j] - nums[i] is less than the target, we increment j to increase the difference; if it is greater than the target, we increment i to decrease the difference. This allows us to traverse the array in a single pass, finding the optimal difference in O(n) time.
Brute Force Approach
The brute-force approach involves checking every possible pair of indices (i, j) with i < j using nested loops, calculating the absolute difference between their value difference and the target, and keeping track of the minimum. This requires checking O(n²) pairs, leading to an inefficient O(n²) time complexity.
Verified Code Solutions
function closestDifferencePair(nums, target) {
let minDiff = Infinity;
let result = 0;
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
let diff = Math.abs(nums[j] - nums[i] - target);
if (diff < minDiff) {
minDiff = diff;
result = Math.abs(nums[j] - nums[i]);
} else if (diff === minDiff) {
result = Math.min(result, Math.abs(nums[j] - nums[i]));
}
}
}
return result;
}class Solution {
public int closestDifferencePair(int[] nums, int target) {
int minDiff = Integer.MAX_VALUE;
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
int diff = Math.abs((nums[j] - nums[i]) - target);
minDiff = Math.min(minDiff, diff);
}
}
return minDiff;
}
}def closest_difference_pair(nums, target):
min_diff = float('inf')
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
diff = abs((nums[j] - nums[i]) - target)
min_diff = min(min_diff, diff)
return min_difffunction closestDifferencePair(nums, target) {
let minDiff = Infinity;
let result = 0;
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
let diff = Math.abs(nums[j] - nums[i] - target);
if (diff < minDiff) {
minDiff = diff;
result = Math.abs(nums[j] - nums[i]);
} else if (diff === minDiff) {
result = Math.min(result, Math.abs(nums[j] - nums[i]));
}
}
}
return result;
}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.