Two Sum - Part 1 - Interview Question

Prerequisite:
Basic Array, Loop, and Big O Knowledge.
( Problem )

Given an integer array and target, return the indices of the two numbers that add up to the target number.

Requirements:
You may not use the same element twice.
( Example )

Let's say we have an array with the following integers (9, 4, 12, 15, 5) and a target of 20.

The problem is asking us which two numbers add up to 20.

In the image below, select two numbers that add up to 20.

If you're like most people, you scanned the numbers until you found two that equaled the target.

Once we find the two numbers that equal the target, we need to get the index of each number and return that as the answer.

If our index numbers start from 0 and go from left to right, what are the two index numbers we need to return?

In the image below, add the correct index numbers under the selected numbers.

That's it. Once we find the two numbers that equal our target, we return an array of their indices.

( Brute Force - Unoptimized Solution )

Similarly to how we scanned the array numbers with our eyes, a computer will need to do the same thing.

To allow the computer to scan the array, we introduce code that loops through each number.

1// Code that loops through each array number
2for(let i=0; i<array.length; i++) {
3 // Gets the number by its array index
4 array[i]
5}

A loop will go through each number in the array, accessing the number by its index.

1for(let i=0; i<array.length; i++) {
2 array[i]
3}

Our looping code works if we only need to find one number at a time, but the solution requires we find two numbers.

( Question )

What should we do next?

A.Make a loop for each number in the array. (5 loops in this case)
B.Add another loop inside our first loop (A nested loop).
C.Add another loop outside our first loop (separate loops).

In this case, we want to add another loop inside our first loop.

Why a nested loop?

Using a nested loop, we can keep one number, while we loop through the remaining numbers looking for a match to our target.

For this problem, we start our second loop at index 1, because we already know what number is at index 0 from our first loop.

Now, the only thing left is to check our two numbers for a match and return an answer if we find one.

1// Compare two numbers
2if (target == array[i] + array[j]) {
3 // Return the match
4 return [i, j]
5}

Here we see if our two numbers add up to the target, and if they do, we return an array of the two indices.

Let's walk through our problem from start to finish.

...

Click Next to walk through the code

...

CodeResult
target
20
i
undefined
j
undefined
array
[9, 4, 12, 15, 5]
array.length
5
( Brute Force Time Complexity )

Let start with a variable n

n equals the number of items in the array.

In our Brute Force approach, we have nested loops, which means, not only will we visit all n items, but for each item, we will visit the remaining items.

Our Brute Force approach ultimately has a Time complexity of O(n^2)

Why is it n^2, when we don't visit all n items in the second loop?

In our problem, we have 5 items total. If we were to visit each item, that would be 5^2 or 25 items.

If we removed the items our second loop skips we are left with roughly half of the total n^2, which would give us an equation something like n^2 / 2

In Big O, we only care about the rate of increase, so we drop constants from the our equation. Leaving us with n^2

Therefore our Time Complexity is O(n^2)

( Space Complexity )

Our space complexity is O(1).

( To be Continue )

Can we provide a better solution to this problem?