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[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²) 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;
    }