Subarray Pair Difference Counter
Problem Description
Given an integer array `values` and an integer `gap`, return the number of pairs `(i, j)` where `i < j` such that `values[j] - values[i] == gap`.
Note that `gap` can be zero or negative.
**Example 1:**
```
Input: values = [3, 1, 4, 1, 5], gap = 2
Output: 2
```
Explanation: Pairs are (0,2): 4-3=1? No. Let's re-check: values[2]-values[0]=4-3=1 ≠ 2. values[2]-values[1]=4-1=3 ≠ 2. values[4]-values[2]=5-4=1 ≠ 2. values[4]-values[0]=5-3=2 ✓. values[4]-values[1]=5-1=4 ≠ 2. values[3]-values[1]=1-1=0 ≠ 2. Actually: (1,2): 4-1=3 no. Let me recompute: pairs with diff 2: (0,4): 5-3=2 ✓, (1,2): 4-1=3 no, (3,4): 5-1=4 no. Hmm only 1 pair.
Let me use a cleaner example.
Input: values = [1, 3, 5, 7, 9], gap = 4
Output: 3
```
Explanation: (0,2): 5-1=4 ✓, (1,3): 7-3=4 ✓, (2,4): 9-5=4 ✓. Three valid pairs.
**Example 2:**
```
Input: values = [2, 2, 2, 2], gap = 0
Output: 6
```
Explanation: All pairs (i,j) with i<j satisfy values[j]-values[i]=0. There are C(4,2)=6 pairs.
Constraints
- 1 <= values.length <= 10^5
- -10^5 <= values[i] <= 10^5
- -2 * 10^5 <= gap <= 2 * 10^5
Follow-up
Can you solve this in O(n log n) using binary search on a sorted prefix to also support queries for absolute difference equal to gap?
Hints
Try the problem first. If you get stuck, you can reveal hints one at a time.
Solution
Leaderboard
No entries yet for python.
Be the first — submit an accepted solution.