Count Number of Pairs With Absolute Difference K

Problem Description

Given an integer array nums and an integer k, return the number of pairs (i, j) where i < j such that |nums[i] - nums[j]| == k.

Key Insights

• The problem requires counting pairs with a specific absolute difference, which can be approached using a hash table for efficient lookups.
• For each element in the array, we can check for the existence of two potential counterparts: nums[i] + k and nums[i] - k.
• Since the constraints are manageable (length of nums up to 200), a straightforward counting approach can be implemented effectively.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we can utilize a hash table (or dictionary) to store the frequency of each number in the nums array. For each element, we check if the numbers that could form a valid pair (i.e., nums[i] + k and nums[i] - k) exist in the hash table. We then count how many times these pairs can be formed based on their occurrences.

1. Initialize a hash table to count occurrences of each number.
2. Iterate through the array and populate the hash table.
3. For each number, check for both num + k and num - k in the hash table and count the pairs.
4. Return the total count of pairs.

Code Solutions