After a period of inactivity due to working full time on a project (this was enough coding for me), I am back writing some articles.
After a week and a half away from work over the Christmas period I quickly fell into the familiar seasonal pattern of not really knowing what day it is, with work looking on the horizon tomorrow I thought I could do with a little sharpener and looked on the Leetcode website for a couple of programming questions to look at, these are two separate questions from the Leetcode site, they are related in nature but require different solutions.
What is the 2Sum Problem?
The problem is written on leetcode as follows;
“Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice.”
So looking at the following example;
Our answer would be array positions 0 and 1 As the values in these positions sum to the target of 9.
Solving the 2Sum Problem
There is a constraint that will help us, based on the problem statement we know there is always only one solution within the array, this means when we find that solution we can return the answer and stop processing. But how will we go about solving this?
Approach One – Brute Force
The first idea you might have to solve this problem – and the most simple conceptually is to brute force it. Imagine we have input as follows;
we could write code to go through every value and see if there is another value that sums to the target from it so in this example we would loop as follows;
- Does 1 + 4 = 13? – No
- Does 1 + 5 = 13? – No
- Does 1 + 8 = 13? – No
- Does 1 + 11 = 13? – No
- Does 4 + 1 = 13? – No
- Does 5 + 4 = 13? – No
- Does 4 + 8 = 13? – No
- Does 4 + 11 = 13? – No
- …..
- Does 8 + 5 = 13? – Yes
Our answer is therefore 2,3 (the index of the values that sum to 13). In this example a brute force approach would actually find the answer fairly quickly, but in a large list the number of iterations would grow exponentially as the size of the array grows, as I am sure you can appreciate from this example. The solution simply isn’t very efficient as it has to loop through the set twice. That being said it does work and could be viable on smaller sets, this solution could be coded as follows;
Here we have 2 loops one looking at every position in the array and the other looking at each value ahead of the position currently one. This prints [2,3] to the console – which as demonstrated earlier in this example is correct.
Approach Two – Using a dictionary
So we have a solution – but it is not very efficient, what we need to do is to find a solution so we only loop through the input array once instead of twice (as we are with the brute force approach). One possible way of doing this is to use a dictionary object to store numbers that the loop has already seen – and evaluate them (the previously seen numbers) for each new number. This use more memory as we are storing data, but should be a lot faster.
Consider the following code;
What we are doing here is the following;
- We create an empty dictionary
- We loop through the input array
- we establish what the difference is between the target and our current number
- if the difference exists in the dictionary – we know the pair of numbers that sum to the target and return the indexes of these
- if we haven’t seen the number we are currently iterating on we add it to the index – thereby building up a history of all the numbers we have looped through – preventing multiple loops.
This returns the answer of [2,3] as expected – with only one pass through the list.
I don’t know if this is the “most optimal” solution to this problem, Its possible you could further optimise the solution by perhaps pruning the original list to remove numbers that you know cannot sum to the target as they are too large for example, but it is significantly better than the brute force approach.
The code shown in screenshots is available on GitHub (2Sum)