# Interview Prep Warmup: Two Sum via LeetCode in PHP

This problem was originally solved on LeetCode.

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.

Example 1:

```Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums + nums == 9, we return [0, 1].
```

Example 2:

```Input: nums = [3,2,4], target = 6
Output: [1,2]
```

Example 3:

```Input: nums = [3,3], target = 6
Output: [0,1]
```

Constraints:

```2 <= nums.length <= 105
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.```

## The Problem: LeetCode’s Two Sum

Given an array of integers and a target value our job is to find the two integers which add up to the target.

A naive approach would potentially look at every integer and compare it to every other integer, giving us a O(n2) runtime.

We can do better.

If we use a hash table we can store each values index and check to see if a value exists in O(1) time. With that: a less naive approach would be to set up a hash table on our first pass, and then loop through the hash table until we find one where `\$hash[\$i] + \$hash[\$nums[\$hash[\$i]]] == \$target`.

This has a slight disadvantage of setting up O(n) additional space.

Not terrible, but can we do better?

Ask yourself: what is happening when we set up the hash table?

What happens with an input like this?

`Input: nums = [3,3], target = 6`

Since we can’t return the same value twice we’ll need to track individual indices.

But you may notice when you set up the hash table: each index is added after any existing ones.

This means we know for sure our current index is not in the hash table yet.

And that means we can take a look at `\$hash[\$nums[\$i]]` for the result and break when we find it.

## My Solution to the Two Sum problem

Here is my solution. It’s written in PHP and runs in O(n) time.

```function twoSum(\$nums, \$target) {
\$hash = [];
\$indices = [null, null];
for (\$index = 0; \$index < count(\$nums); \$index++) {
\$number = \$nums[\$index];
\$remainder = \$target - \$number;
if (isset(\$hash[\$remainder])) {
\$indices = \$hash[\$remainder];
\$indices = \$index;
break;
}
\$hash[\$number] = \$index;
}
return \$indices;
}```