Solving: findPairsWithGivenDiff

In this article, I’ll be breaking down the findPairsWithGivenDiff problem in Javascript. I’ll walk through my process and solve the problem in two ways to compare their BigO.

Let's begin!

Directions:

“Given an array arr of distinct integers and a non-negative integer k, write a function findPairsWithGivenDifference that returns an array of all pairs [x,y] in arr, such that x - y = k. If no such pairs exist, return an empty array.

Note: the order of the pairs in the output array should maintain the order of the y element in the original array.”

Let’s analyze and restate the problem in our own words.

The inputs are an array of distinct integers and a non-negative integer.

We’d like to know how many pairs provide a difference of the given non-negative integer ‘k’. Such that (x-y) = k.

The outputs should be an array of arrays if such pairs exist. Each sub-array containing the [x, y] values. If no pairs exist return an empty array.

The placement of the sub-arrays should follow the index of the ‘y’ value within the [x, y] sub-array.

Start with the naive approach.

Let's walk through how we could solve this.

If we used a nested loop to iterate through each integer within the array and subtract it from itself we can then have a simple if statement to see if the two values pass our condition of (x-y) = k. Once we’ve found the right pairs we can add them to a results array. To fit the index condition, since we’re in a loop, we can use the iteration value (aka index) to place the pairs in the correct sequence, then filter out the empty values once it is filled.

Now let's look at the bigO.

The naive solution has a bigO of O(n²) because we have a nested loop iterating over the same array. The filter is another iteration but as the input size scales, we can ignore its impact comparatively. While the array we created for the result has a bigO of O(n) for insertion, search, and deletion of empty values.

So this works — if you came up with this solution that's awesome.

But how could we work it harder? better? faster? stronger?

Well, the first thing we want to get rid of is the nested loop… Let's look at what we’re actually doing in the nested loop. So if we’re going through the loop what are we actually doing?

We’re looking for a number that will produce the difference of ‘k’.

What’s another way to do that?

…

…

Well we know that

If → (x-y) = k

Then → (x-k) = y

So instead of calculating which values produce ‘k’ with nested loops, what if we just looked up the value we needed from a map?

Since we know that (x-k) will provide the matching ‘y’, we can calculate both ‘x’ and ‘y’ with just ‘x’ and ‘k’. So with a single loop we can create a hash map that maps all the possible ‘y’ values with its corresponding ‘x’ value. So we have a map that produces key-value pairs of {y: x}.

Once the map is populated, we can iterate through the array again, and simply lookup if the current value exists within the map. If it does, then we know that there is a matching ‘x’ within the array. i.e. since the value within the current iteration exists within the map if becomes our ‘y’, and since we calculated our ‘y’ with an ‘x’ value when we populated the map we know that both exist within the given array.

Let's see the code:

A few notes:

Since we’re iterating once through the array starting on line 15, we can simply push the pair into the array and no longer need to eliminate any null values with a filter.

Because we mapped all the values, the keys are converted to strings, so we need to make sure that the values we push into the results array are actually integers. We can use parseInt to convert the string representation to integers.

We use parseInt on the ‘y’ value as well as the ‘x’ value because on line 13, we’re actually setting the value to the key to a string. This is important for an edge case where the ‘y’ value equals zero.

On line 17 we have a short-circuit evaluation, and if the diffMap[arr[i]] returns zero, it will evaluate to false and not actually be pushed into the results array. By converting it to a string when the map is being populated we avoid that case.

The BigO

By leveraging a hash map we’ve improved the time complexity to O(n*log(n)) for the worst case and O(n) for the average case. While the space complexity remains O(n) since the size of the output itself is O(n), and since the map we made will only hold n elements, it won’t increase the space complexity.

Hope this helps you with you’re next algo!