Count pairs whose difference is at most k
Coding problemMediumAsked in: Amazon
Given a list of integers nums and a whole number k, count the pairs of positions i < j where the absolute difference between nums[i] and nums[j] is at most k. (The absolute difference ignores the sign: 3 and 5 differ by 2, and so do 5 and 3.)
Pairs are counted by position, so equal values at different positions form separate pairs. The count can be larger than a 32-bit integer can hold, and the difference of two values can be too.
Examples
Example 1
Input: nums = [1,5,3,9], k = 2
Output: 2
The pairs (1, 3) and (3, 5) differ by 2. Every other pair differs by more.
Example 2
Input: nums = [4,4,4], k = 0
Output: 3
Each of the three pairs of positions holds equal values.
Example 3
Input: nums = [], k = 7
Output: 0
Constraints
- The list holds between 0 and 100,000 integers
- Each value is a 32-bit integer
- 0 <= k <= 2,147,483,647
Run checks the 3 examples. Submit also runs the hidden tests: edge cases, large inputs and a time limit.
Run your code to see the results here. Ctrl or Cmd + Enter runs; add Shift to submit.