Solving: FindDuplicates

In this article, I’ll be breaking down the FindDuplicates problem in Javascript. Then I’ll walk through my process of solving the problem and discuss its BigO.

Let’s begin!

Question

Given two sorted arrays arr1 and arr2 of passport numbers, implement a function findDuplicates that returns an array of all passport numbers that are both in arr1 and arr2. Note that the output array should be sorted in ascending order.

Let N and M be the lengths of arr1 and arr2, respectively. Solve for two cases and analyze the time & space complexities of your solutions: M ≈ N - the array lengths are approximately the same M ≫ N - arr2 is much bigger than arr1.

Example:

input:  arr1 = [1, 2, 3, 5, 6, 7], arr2 = [3, 6, 7, 8, 20]

output: [3, 6, 7] # since only these three values are both in arr1 and arr2

In this problem, we are given two sorted arrays… We are tasked to find all the numbers that exist in both arrays and return them within a new array in ascending order.

Now given that both arrays are sorted, there is a specific sorting algorithm that immediately comes to mind: binary search.

So thinking along these lines, how can we leverage the binary search algorithm to help us?

We can use binary search to determine if a given value exists within an array. So if we loop through a single array and plug each value into a binary search function, that searches through the 2nd array, we could easily determine if the value exists. If it does we can push that value into a new results array. Given that both arrays are sorted, simply iterating through one array from left to right will allow us to create a results array in the proper ascending order.

*if you’re not familiar with Binary Search, take a moment to look at this article here

Alright, that sounds like a solid plan, let’s code it out!

In the function above, we start by instantiating a results array to store the numbers seen in both arr1 and arr2.

We then create an arrow function binarySearch that will search through arr2 for a value we call ‘seek’.

Afterward on line 62, we start our for loop, iterating through arr1. With each iteration, we pass in the number — ‘val’ — to our binarySearch function, and if it returns true we push the number into our results array.

At the end of the loop, we return the results array.

Pretty simple once you realize how to implement and utilize binary search.

Complexity

Because we are running a binary search on arr2 N times, we have a time complexity of O(N x log(M)) → binary search = log(M), running it N times → O(N x log(M)).

And since it is possible that the entire smaller array can exist within the larger array the space complexity is O(N), with N being the size of the smaller array.

Final Thoughts

When I first approached this problem, I thought I could use a combination of loops and hashes to solve the problem. But then I noticed the keyword sorted in the question. If you’re not familiar with binary search I highly recommend getting to know it and thinking of it whenever you’re searching within a sorted array — it’s likely a good option to consider!

Hope this helps you out on your next algo. Happy Hacking!