Find If Pair in An Array Exists That Sum to a Specific Value

In today’s post, I will be discussing an actual interview question related to arrays.

Suppose, you are given an array like this:

[2, 9, 5, 6, 3, 8, 2] and you have to find out if a pair exists in the array such that their sum equals 9.

As a candidate, you need to understand the question properly. You need to make sure that you have understood the question by asking him back. You have to repeat the question in your own words and make sure you understood the question.

Next, you need to come up with a solution to the problem. Don’t worry if the solution is optimal or not. Many times candidates think of an answer but they don’t tell it because they think it’s not the best solution so why should I bother telling it. Right?

Well, that’s not the correct approach.

The first thing that you should do is to give a solution whether it’s optimal or not.

So in this case, the first solution that comes to my mind is a nested loop.

I can run a for loop and then another nested for loop and check if each pair is equal to the sum or not. If I find such a pair I return true and exit out of the loop. If I don’t find such a pair, I return false.

Pseudo Code:

for loop i = 0 -> n

for loop j = 1 -> n

if arr[i] + arr[j] == sum -> return true

If no such value found in array

return false.

The algorithmic run time complexity for this program above will be O(n^2).

At the point, the interviewer might ask you how can you better than this O(n^2) complexity.

So now you can think about a more optimal solution.

So the next solution comes to mind is using a HashSet.

You can loop through the array. For each element, if (sum – element) exists in HashSet return true.

Otherwise, if the element doesn’t exist in Hashset, then add it to the hashset.

If the loop is over and no such element found then return false.

At this point, the interviewer might ask you the complexity of this solution.

Since it’s a single for loop, and look up in HashSet is O(1), the run time complexity of the algorithm will be O(n).

Now, if the interviewer likes your solution, he/ she might ask you to write the code for it on whiteboard.

Before you jump on to code, you might also wanna check for edge cases. In what all scenarios can your algorithm fail?

For example, if the array doesn’t have any elements? What happen when array has only one element? What happens in case of negative numbers?

Once you have identified the edge cases, you might wanna list those too as well. At this point, the interviewer might ask you to add those edge conditions’ checks to your code or he might ask you to skip those in the interest of time.

In my code, I am still going to add those as well.

Here is the GitHub link to the code.

At the end, you should test the code with an example and make sure it’s doing what you intend it to do. If you follow all these steps you will have successfully answered the interview question.

For more such interview questions and practicing how to answer them in a technical interview, please subscribe to my blog and Youtube channel here.