# 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`

, returnindices of the two numbers such that they add up to.`target`

You may assume that each input would have

, and you may not use theexactlyone solutionsameelement 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[0] + nums[1] == 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(n^{2}) 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[0] = $hash[$remainder]; $indices[1] = $index; break; } $hash[$number] = $index; } return $indices; }