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.

The absolute difference of two integers a and b is the absolute value of a - b.

Example:

Example:

Example:

Constraints:

Clarifying Questions

  1. Q: Should we consider only unique pairs? A: Yes, each pair (i, j) should satisfy i < j.

  2. Q: Can k be zero? A: No, based on the constraints 1 <= k <= 99, k cannot be zero.

  3. Q: Are duplicates allowed in the input array nums? A: Yes, the array can have duplicate values.

Strategy

The problem requires us to count pairs where the absolute difference between elements is exactly k. We can solve this problem using a brute force approach by checking all possible pairs and counting those satisfying the condition. Given the constraints, this approach will be efficient enough.

Steps:

  1. Iterate through each possible pair (i, j) in the array where i < j.
  2. Check if |nums[i] - nums[j]| == k.
  3. If the condition holds, increment the count.

Pseudo-code:

count = 0
for i from 0 to len(nums) - 1
    for j from i + 1 to len(nums)
        if |nums[i] - nums[j]| == k
            increment count
return count

Time Complexity:

The time complexity of this approach is O(n^2) where n is the number of elements in the array nums. This is because we are checking all possible pairs which involves a nested loop.

Code

#include <vector>
#include <cstdlib> // for abs function

int countKDifference(std::vector<int>& nums, int k) {
    int count = 0;
    int n = nums.size();
    
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (std::abs(nums[i] - nums[j]) == k) {
                ++count;
            }
        }
    }
    
    return count;
}

Example Usage:

#include <iostream>

int main() {
    std::vector<int> nums1 = {1, 2, 2, 1};
    int k1 = 1;
    std::cout << "Example 1: " << countKDifference(nums1, k1) << std::endl; // Should output 4

    std::vector<int> nums2 = {1, 3};
    int k2 = 3;
    std::cout << "Example 2: " << countKDifference(nums2, k2) << std::endl; // Should output 0

    std::vector<int> nums3 = {3, 2, 1, 5, 4};
    int k3 = 2;
    std::cout << "Example 3: " << countKDifference(nums3, k3) << std::endl; // Should output 3

    return 0;
}

This code first defines the function countKDifference which implements the described algorithm to count the pairs with absolute difference k. The main function demonstrates the usage with example inputs.

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