 Published on
 6 min read
Two Sum Leetcode
The prompt
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.
You can return the answer in any order.
Examples
Example  Input  Target  Output 

1  [2,7,11,15]  9  [0,1] 
2  [3,2,4]  6  [1,2] 
3  [3,3]  6  [0,1] 
Constraints
2 <= nums.length <= 104
& 109 <= nums[i] <= 109
& 109 <= target <= 109
Only one valid answer exists.
Solution #1: (Naive)
two_sum_naive.py
def naive_two_sum(nums: List[int], target: int) > List[int]:
for num in range(len(nums)):
for n in range(len(nums[num + 1:])):
if nums[num] + nums[n + num + 1] == target:
return [num, n + num + 1]`}
Since this is a naive solution, we can use nested loops.
The first loop simple iterates over the array as usual, we will call this loop the
parent loop. Now the second one, or
child loop
is a little bit more tricky. The second loop will loop through the remainder of the the array after
the first loop goes over the
nth
element.For example:
Let's assume we have
nums = [1,2,3,4]
and the target is 6.The first loop will start at index 0, in this case accessing "1".
Elements:Indexes:
10
21
32
43
Now the second loop, loops through an array that start after the index of the parent loop.
Because the parent loop current index is 0 the second loop start at index 1. In simpler terms
we will always slice the array, starting at the current index of the parent loop and adding 1.
So it would look something like this:
Elements:Indexes:
20
31
42
Same Array
Do note that we are using the exact same array.
If the parent loop current index is 2 then the child loop starts at index 3, you get the idea.
Last Example, let's say we have an arryay of 6 elements, and the parent loop is in the 4th iteration or at index 3.
Elements:Indexes:
20
31
42
53
64
75
Our child loop will continue looking at the remainder of the same array, but starting at index 4 as shown below.
Elements:Indexes:
20
31
42
53
64
75
Now that we understand the logic behind the nested loop we
can start comparing the values until we find the two numbers
that match the target.
To do this we need to simply access the value from the parent loop and
the child loop and compare them with a simple
if
statement.As you can see in line 4 of the Naive Solution, we compare the element at the parent loop current index vs
the element of the child loop at the current
parent index + the current child index + 1
.This might be a bit confusing let's break it down based on the last example.
Becuase the parent loop is current at index 3, we access the element with the value of 5. In Python
you can do so by
nums[num]
where nums is the array and num is the index.Now to access the element of the child loop we need to do some math. In Python it would look like
nums[num + n + 1]
where nums
is the array, num
is the index of the parent loop (3 in this case), n
is the index of the
child loop (0 in this case) and lastly we add 1. So if we add all of it together, we should get nums[4]
.nums[num + n + 1] or nums[4] is 6`}
Time Complexity  Space Complexity 

O(n²)  O(1) 
Solution #2: (HashMap)
two_sum_hashmap.py
def hash_two_sum(nums: List[int], target: int) > List[int]:
hash_map = {}
for i, num in enumerate(nums):
remainder = target  num
if hash_map.get(remainder) != None:
return hash_map.get(remainder), i
hash_map[num] = i
Enter hash map!
Out of the box thinking at it's best.
If this solution never crossed your mind before,
don't worry you are not alone.
Alright enough chit chat...
We will complete this one with only one for loop.

First we need to create a variable to hold our dict... Sorry I meant our hash map...

After we have our hashmap ready we start our loop. Our loop must have index, because we will be using the values in the array as keys and the index as our values for our hash map. If you are solving this with python, have a look at the
enumerate()
function. It's pretty nice. 
The trick is perform by subtracting the current element from the target.

Then adding the element to the hashmap.

And finally trying to check if the remainder of our subtracting is a key in our hashmap.
I know it's a bit confusing, but we'll go over it now.
In Line 2 of the code snippet above we simple create a new python dictionary (hashmap). In
Line 4
we start our loop with enumerate to get both the index and the value. (In that order).
Line 5
is where we create our
remainder
variable to hold the reminder of the target  num
, num being the
value.
Line 6
is where we try to get the remainder from the hashmap. In python we use get to avoid KeyValue Errors
.
If we are able to get the key, that means we have two numbers that add up to the target. Soooo...
Line 7
returns the index of both numbers.
Line 8 , if the num was not in the hashmap, we simple add it at the end of the
iteration.Time Complexity  Space Complexity 

O(n)  O(n) 
And that's it! Hopefully that wasn't too bad!
See you on the next problem!
For more problems like this one be sure to checkout NeetCode.