Q2. Pairs with Given DifferenceSolved

Problem Description

Given an one-dimensional integer array A of size N and an integer B.

Count all distinct pairs with difference equal to B.

Here a pair is defined as an integer pair (x, y), where x and y are both numbers in the array and their absolute difference is B.

Problem Constraints

1 <= N <= 104

0 <= A[i], B <= 105

Input Format

First argument is an one-dimensional integer array A of size N.

Second argument is an integer B.

Output Format

Return an integer denoting the count of all distinct pairs with difference equal to B.

Example Input

Input 1:

 A = [1, 5, 3, 4, 2]
 B = 3

Output 1:

 2

Explanation 1:

 There are 2 unique pairs with difference 3, the pairs are {1, 4} and {5, 2}

Input 2:

 A = [8, 12, 16, 4, 0, 20]
 B = 4

Output 2:

 5

Explanation 2:

 There are 5 unique pairs with difference 4, the pairs are {0, 4}, {4, 8}, {8, 12}, {12, 16} and {16, 20}

Input 3:

 A = [1, 1, 1, 2, 2]
 B = 0

Output 3:

 2

Explanation 3:

 There are 2 unique pairs with difference 0, the pairs are {1, 1} and {2, 2}.

Solution

Observations

1. From Example 1

   1. To get 3, for each element in A, we must have A[i]+3 or A[i]-3 in the array
   2. But checking in an array takes O(n) time
   3. So we create a set called elementsSet that has all distinct elements

2. For each element in A we have a pair of Target elements. So we create two variables to store the values.

   1. targetElement1 = A - B
   2. targetElement2 = currentElement + B

3. If elementsSet has targetElement1 , we have successfully found a pair !!

   1. We declare another Set called distinctPairs. It contains all the unique pairs found as strings
   2. Add this pair to distinctPairs.

4. Similarly, If elementsSet has targetElement2 , we have successfully found another pair !!

   1. Add this pair to distinctPairs.

      <aside> 💡 REVERSE the order this time to avoid duplicate entries in the array

      </aside>

5. Return the size of the distinctPairs set

Code

solve : function(A, B){
    let elementsSet = new Set();

    let distinctPairs = new Set();

    for (let i = 0; i < A.length; i++) {
        const currentElement = A[i];
        const targetElement1 = currentElement - B;
        const targetElement2 = currentElement + B;

        if (elementsSet.has(targetElement1)) {
            distinctPairs.add([targetElement1, currentElement].toString());
        }
        if (elementsSet.has(targetElement2)) {
            distinctPairs.add([currentElement, targetElement2].toString());
        }

        elementsSet.add(currentElement);
    }

    return distinctPairs.size;
}