algoadvance

Leetcode 2006. Count Number of Pairs With Absolute Difference K

Problem Statement

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.

Clarifying Questions

1. Input Constraints:
   • What is the range of values for elements in the array nums?
   • What is the range for k?
2. Output:
   • Should the function return only the count of such pairs?
3. Edge Cases:
   • How should the function handle an empty array or an array with only one element?

Example

Let’s consider an example to clarify:

Input: nums = [1, 2, 2, 1], k = 1
Output: 4
Explanation: The pairs with absolute difference 1 are:
- (0, 1) -> 1 - 2 = -1 (abs: 1)
- (1, 2) -> 2 - 2 = 0 (not counted)
- (0, 3) -> 1 - 1 = 0 (not counted)
- (1, 3) -> 2 - 1 = 1
- (2, 3) -> 2 - 1 = 1

Strategy

We will use a HashMap to keep track of the frequency of the numbers we’ve encountered so far. This will allow us to efficiently find the number of pairs with the desired absolute difference.

1. Initialize an empty HashMap to keep count of each number we encounter.
2. Iterate through the array, for each number:
   • Check if there exists a number in the HashMap such that the absolute difference with the current number is k.
   • Add to the count based on the frequency of such numbers.
   • Update the HashMap with the current number.
3. Return the count of such pairs.

Code

import java.util.HashMap;

public class NumberOfPairsWithDifference {
    public int countKDifference(int[] nums, int k) {
        HashMap<Integer, Integer> countMap = new HashMap<>();
        int count = 0;
        
        for (int num : nums) {
            // Check pairs where difference is `k`
            if (countMap.containsKey(num - k)) {
                count += countMap.get(num - k);
            }
            if (countMap.containsKey(num + k)) {
                count += countMap.get(num + k);
            }

            // Update the map with the current number
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }
        
        return count;
    }
    
    public static void main(String[] args) {
        NumberOfPairsWithDifference solution = new NumberOfPairsWithDifference();
        int[] nums = {1, 2, 2, 1};
        int k = 1;
        int result = solution.countKDifference(nums, k);

        // Expected output is 4
        System.out.println("Number of pairs: " + result);
    }
}

Complexity Analysis

• Time Complexity: The solution iterates through the array exactly once, and for each element, performs constant-time operations using the HashMap. Hence, the time complexity is O(n), where n is the length of the input array nums.
• Space Complexity: The space complexity is also O(n) due to the additional HashMap that potentially stores every element of the array.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?