Frontend School

Count Pairs with Target Difference in Sorted Array (Two Pointers)

DSA
easy

Count Pairs with Target Difference in Sorted Array (Two Pointers)

Easy
Two Pointers
Arrays
Counting
Algorithms
Coding-Interview
practice

Overview

This problem challenges you to efficiently count pairs in a sorted array that have a specific absolute difference using the two-pointer technique. Given a sorted array of distinct integers and a non-negative target difference k, your task is to find how many unique pairs (nums[i], nums[j]) exist such that i < j and nums[j] - nums[i] == k.

What you need to do / Task

Implement the function countTargetDifferencePairs that takes a sorted array of distinct integers nums and a non-negative integer k as input. Your function should return the total count of unique pairs (nums[i], nums[j]) where i < j and their difference nums[j] - nums[i] is exactly k.

Input & output

Input:

  • nums: A number[] representing a sorted array of distinct integers.
  • k: A number representing the non-negative target difference.

Output:

  • A number representing the total count of pairs satisfying the condition.

Clarifications

  • What if k is negative? The problem specifies k will always be a non-negative integer.
  • Can nums contain duplicate numbers? No, the input nums array will contain distinct integers only.
  • What if no such pairs are found? If no pairs satisfy the condition, the function should return 0.
  • What if the array nums is empty or has only one element? In such cases, no pairs can be formed, so the function should return 0.
  • What does i < j mean? It ensures that each pair (nums[i], nums[j]) is counted once and that nums[j] always comes after nums[i] in the array.

Examples

1

Example 1

Input:

nums = [1, 3, 5, 7], k = 2

Output:

3

Note:

The pairs are (1,3), (3,5), and (5,7). Their differences are 2, 2, and 2 respectively.

2

Example 2

Input:

nums = [1, 2, 3, 4, 5], k = 1

Output:

4

Note:

The pairs are (1,2), (2,3), (3,4), and (4,5). All have a difference of 1.

3

Example 3

Input:

nums = [1, 5, 9, 13], k = 4

Output:

3

Note:

The pairs are (1,5), (5,9), and (9,13). All have a difference of 4.

4

Example 4

Input:

nums = [1, 2, 3], k = 5

Output:

0

Note:

No two numbers in the array have a difference of 5.

Constraints

Constraints & assumptions

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • nums is sorted in non-decreasing order.
  • All elements in nums are distinct.
  • 0 <= k <= 2 * 10^9

What graders evaluate

  • Correctness: The solution must accurately count all pairs satisfying the nums[j] - nums[i] == k condition.
  • Efficiency: The solution should run in optimal time complexity, ideally O(N) where N is the length of nums.
  • Edge Cases: Proper handling of scenarios like an empty nums array, an array with only one element, or when no valid pairs exist.
  • Algorithm Application: Effective use of the two-pointer technique to leverage the sorted nature of the input array.

Loading editor...