We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Number of Pairs With Absolute Difference K

Number: 2116

Difficulty: Easy

Paid? No

Companies: Google, tcs, Expedia, Goldman Sachs, Amazon, Oracle

Problem Description

Given an integer array nums and an integer k, we are required to return the number of pairs (i, j) where i < j such that the absolute difference |nums[i] - nums[j]| equals k.

Key Insights

  • Use a frequency table (hash table) to count the occurrences of each number.
  • For each unique number, check if the number + k exists in the frequency table.
  • Multiply the frequencies of number and number+k to get the count of valid pairs for that particular value.
  • Since k is always >= 1, we can safely use the frequency method without worrying about handling the k == 0 case.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the array, as we traverse the list once to build the frequency table and then iterate over a limited range of possible values. Space Complexity: O(n) in the worst-case scenario for storing the frequency counts.

Solution

We use a hash table (or dictionary) to count the occurrences of each number in the array. For each unique number in the hash table, we look for the number + k in the table. If it exists, then every occurrence of the current number can pair with every occurrence of (current number + k). Multiplying these two counts gives the number of valid pairs for that number. The total pair count is the sum of valid pairs from all numbers.

Code Solutions

# Python solution

def countPairsWithDiffK(nums, k):
    # Create a dictionary to store frequency counts of each number
    frequency = {}
    for num in nums:
        # Increment the count of the current number in frequency table
        frequency[num] = frequency.get(num, 0) + 1

    count = 0
    # For each unique number, check if the number+k exists in the frequency table
    for num in frequency:
        target = num + k
        if target in frequency:
            # Add the product of occurrences of num and target to the final count
            count += frequency[num] * frequency[target]
    return count

# Example test cases
print(countPairsWithDiffK([1,2,2,1], 1))  # Output: 4
print(countPairsWithDiffK([1,3], 3))        # Output: 0
print(countPairsWithDiffK([3,2,1,5,4], 2))  # Output: 3
← Back to All Questions