mediumTwo PointersPattern: Two Pointer Search (Same Direction)
Closest Difference Pair Solution
Problem Statement
You are given a 0-indexed sorted integer array nums and a target integer target. You need to 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
Example 1:
Input:nums = [1, 4, 10, 15, 22], target = 8
Output:1
Explanation: For index pair (0, 2), nums[2] - nums[0] = 10 - 1 = 9. The absolute difference is |9 - 8| = 1. No other pair gives a smaller absolute difference.
Example 2:
Input:nums = [2, 5, 8, 12], target = 5
Output:1
Explanation: For index pair (0, 2), nums[2] - nums[0] = 8 - 2 = 6, with absolute difference |6 - 5| = 1.
Constraints
- 2 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- nums is sorted in non-decreasing order.
- 0 <= target <= 10^9
Time: O(n) Space: O(1)
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.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
No solution code is currently loaded.
Complete this code in the workspace editor.