0
\$\begingroup\$

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(N2) 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(N2) 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!

\$\endgroup\$

2 Answers 2

1
\$\begingroup\$

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?

\$\endgroup\$
1
  • \$\begingroup\$ Thanks! That was very useful. My previous code actually passed through the entire array two times, not only a "index + 1" sliced array, maybe in this case isn't the same time complexity to complete the algorithm, but I'll keep my eye open to these situations! And I'm using PHP to get used to the syntax hehe \$\endgroup\$ Apr 23, 2022 at 19:00
1
\$\begingroup\$

You can see that your solution is indeed O(N2), 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(N2).

Your code is actually on the inefficient side of O(N2), 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]];
        }
    }
}
\$\endgroup\$
9
  • \$\begingroup\$ I'm sure I don't follow the math here. My high school taught me that N * N = N2, so how can N * N / 2 possibly = N2? Additionally, N + N = 2N, so how can it be true that N + (N * 1) = N? \$\endgroup\$ Apr 23, 2022 at 22:13
  • 1
    \$\begingroup\$ @mickmackusa The point of big-O notation is to ignore constant factors. \$\endgroup\$ Apr 23, 2022 at 22:16
  • 2
    \$\begingroup\$ @mickmackusa N+N=2N. O(2N) = O(N), because you can ignore constant factors. \$\endgroup\$ Apr 23, 2022 at 22:20
  • 1
    \$\begingroup\$ Your algorithm returns the values themselves, but the problem statement says you must return the indexes of the values. so twoSum([5, 3], 8) must return [0, 1], but your code returns [5, 3]. \$\endgroup\$
    – Gabriel
    Apr 23, 2022 at 23:31
  • 1
    \$\begingroup\$ @Gabriel Good catch! Fixed in Rev 2. \$\endgroup\$ Apr 23, 2022 at 23:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.