Count Pairs with Difference At Most K

ArraySliding WindowTwo Pointers

Given a 0-indexed sorted array of integers nums and a non-negative integer k, return the total number of index pairs (i, j) such that 0 <= i < j < nums.length and nums[j] - nums[i] <= k.

Your solution should take advantage of the sorted property of the array to solve the problem in linear time using the two-pointer technique.

Example 1

Input

[
  "[1, 2, 3, 5, 8]",
  "3"
]

Output

Explanation. The valid index pairs (i, j) with difference <= 3 are (0,1), (0,2), (1,2), (1,3), (2,3), and (3,4).

Example 2

Input

[
  "[1, 5, 10, 15]",
  "2"
]

Output

Explanation. No pair of elements has a difference of 2 or less.

Example 3

Input

[
  "[2, 2, 2, 2]",
  "0"
]

Output

Explanation. All 6 pairs of indices have elements with a difference equal to 0, which is <= 0.

Example 4

Input

[
  "[1, 4, 7, 10]",
  "3"
]

Output

Explanation. The pairs (0,1), (1,2), and (2,3) each have a difference of exactly 3.

Example 5

Input

[
  "[10]",
  "5"
]

Output

Explanation. An array with fewer than 2 elements has no valid index pairs.

Follow-up: How would you solve this problem if the array were not pre-sorted, and what would be the resulting time complexity?

Constraints:

1 <= nums.length <= 10^5 0 <= nums[i] <= 10^9 nums is sorted in non-decreasing order. 0 <= k <= 10^9

Views: 7