Algorithm for twoSum

Question

This is my PHP algorithm for the twoSum problem in leetCode:

function twoSum($nums, $target) {
    foreach($nums as $key1 => $num1) {
        foreach(array_slice($nums, $key1 + 1, null, true) as $key2 => $num2) {
            if ($num1 + $num2 === $target) {
                return [$key1, $key2];
            }
        }
    }
}

Its purpose is to take an array and check if the sum of two distinct elements can result in the $target. Just like:

twoSum([2,7,11,15], 9);
// this sould return [0, 1] because 2 + 7 is 9

Initially I created an algorithm that compare the elements in $nums through brute force. Knowing that O(N²) is not that good for time complexity, I tried to refactor it and came up with the solution above. I don't think that the code still with O(N²) time complexity, but I can't think how I could calculate this algorithm in Big O Notation, I would like to know if:

• Can you clearly explain what is the time complexity of this algorithm and why.
• The way this code works still is considered brute force.

Any other advice is very welcome!

Answer 1

Hopefully it's obvious that the "worst case" runtime will happen when there is no matching pair in $nums.^{* **}

In that situation, every (unordered) pair of numbers in $nums will be tested, so clearly the algorithm is still \$O(n^2)\$.

"Brute force" is a subjective term; I would certainly consider this to be a brute-force algorithm. I suspect your first solution was something like this?

for i from 0 to len(nums):
  for j from i+1 to len(nums):
    check if nums[i]+nums[j] == target

You need to be able to see that your new code is the same algorithm.

To get this in sub-quadratic time, you'll need to figure out a way to reliably not do most of the comparisons.

I'm not sure what your background is or what your motivation to use PHP was; for what it's worth I don't think PHP is a good tool for problems like this.

^{* By "hopefully it's obvious" I mean "I'm too lazy to prove it".}

^{** In which case what happens? Is return null how you want to handle failure?}

Answer 2

You can see that your solution is indeed O(N²), because:

• The outer loop goes through N elements.
• For each iteration of the outer loop, the inner loop goes through, on average, N/2 elements.

Altogether, then, in the worst case where you encounter the solution at the end (or if you never encounter a solution), you go through \$N × \frac{N}{2}\$ elements, which makes it O(N²).

Your code is actually on the inefficient side of O(N²), since you call array_slice(), which creates a temporary copy of the subarray — an operation that is O(N).

A better strategy is to take advantage of PHP's associative arrays, such that you can call array_key_exists() to see if the number you are looking for is present, in O(1) time. The suggested solution below should be O(N), because:

• array_flip() is O(N)
• The outer loop is O(N)
• The array_key_exists() test within the loop should be O(1).

Therefore, O(N) + O(N × 1) should be O(N).

function twoSum($nums, $target) {
    $set = array_flip($nums);
    foreach ($nums as $i => $n) {
        if (array_key_exists($target - $n, $set) && $set[$target - $n] != $i) {
            return [$i, $set[$target - $n]];
        }
    }
}