Interview Prep Warmup: Two Sum via LeetCode in PHP
This problem was originally solved on LeetCode.
Given an array of integers
nums
and an integertarget
, return indices of the two numbers such that they add up totarget
.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(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[0] = $hash[$remainder]; $indices[1] = $index; break; } $hash[$number] = $index; } return $indices; }