Find a pair with the given difference in JavaScript

Different approaches to solve this problem

Photo by freestocks on Unsplash

Approach 1: Using two for loops

1. This function will take an array (arr) and a number (diff) as arguments (diff is the difference)
2. Create a for loop to iterate over the array and create a temporary variable to store the sum of the current element of the array (arr[i]) and the difference (diff)
3. Create another for loop nested in the previous one. Check if any number is equal to the temporary variable created in the previous step.
4. If yes, then return true
5. Else return false

Time Complexity: O(n²)

Space Complexity: O(1)

Approach 2: Sorting and Binary Search

1. This function will take an array (arr) and a number (diff) as arguments (diff is the difference)
2. Sort the array in the ascending order
3. Create a for loop to iterate over the array and create a temporary variable to store the sum of the current element of the array (arr[i]) and the difference (diff)
4. Use binary search to find the temporary variable
5. If the answer isn’t -1 then return true
6. Else return false

Time Complexity: O(n log(n))

Space Complexity: O(1)

An optimized version of approach 2

1. Sort the given array.
2. Create two variables i and j and initialize them to 0 and 1.
3. Iterate over the array and check

• If arr[j]- arr[i]is smaller than diff, we need to look for greater arr[j], so increment j by one.
• If arr[j]- arr[i]is greater than diff, we need to look for greater arr[i], so increment i by one.

Note: In both approaches, the first step (sorting the array) takes the same time i.e. O(n log n). But in the second step, the first approach takes the same time, whereas the second approach does the same thing in O(n) time.

Approach 3: Using a hashmap

1. This function will take an array (arr) and a number (diff) as arguments (diff is the difference)
2. Create a new hashmap
3. Iterate through the array and add the values in this hashmap
4. If the difference is zero, keep checking if any element occurs twice. If yes then return true
5. Check if the difference is zero and there are no duplicates then return false
6. Loop over the array and find the sum of the current element in the array and the diff
7. If hashmap has this sum then return true
8. Else return false

Time Complexity: O(n)

Space Complexity: O(n)

Also read,

Square Root of an Integer in JavaScript