Skip to main content

Subarray Pair Difference Counter

medium
ArrayHash TableCountingHashmap Lookup
Asked atAmazonGoogleBloomberg

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.