Leetcode Two Sum Question: Difference of For and While Loop

Question

Here is the question in case:

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.

My Question:

I came up with two different solutions (one using for loop, and the other using while loop) to this question but I believe that they are doing the same operation. They are both brute forcing all possible combinations while avoiding duplicate combinations. However, the first solution will give me a "time limit exceeded" error with large arrays as where the second works fine. I'm not sure what the difference is, they should both be O(n^2)??

num1 = 0
while num1 < len(nums):
    num2 = num1+1
    while num2 < len(nums):
        sum = nums[num1] + nums[num2]
        if sum == target:
            return [num1, num2]
        else:
            num2 += 1
    num1 += 1

for num1 in range(len(nums)):
    for num2 in range(len(nums)):
        if num2 > num1:
            if nums[num1] + nums[num2] == target:
                 return [num1, num2]

Mechanic Pig · Answer

In the two iterative indexing methods in the example you provided, the while loop is usually 3 to 4 times slower than the for loop because:

Each loop of while has an explicit comparison: num1 <
Each loop of while has an explicit function call: len(nums) (this step is actually unnecessary in the while loop. You can use a variable to cache the result of the call)
Each loop of while has an explicit index increment: num1 += 1

You won't see these in the for loop. What the for loop does is:

Call len(nums) once to get the stop of range
Call range() once to build range object
Iterate the iterator of range, and store the result of per loop in i

The standard Python interpreter is implemented in C. it translates the python source code into bytecode and executes it in a C-language virtual machine. Each explicit operation corresponds to a python bytecode:

less than comparison corresponding COMPARE_OP:

>>> dis('a < b')
  1           0 LOAD_NAME                0 (a)
              2 LOAD_NAME                1 (b)
              4 COMPARE_OP               0 (<)
              6 RETURN_VALUE

calling len function corresponding CALL_FUNCTION:

>>> dis('len(nums)')
  1           0 LOAD_NAME                0 (len)
              2 LOAD_NAME                1 (nums)
              4 CALL_FUNCTION            1
              6 RETURN_VALUE

incrementing index corresponding INPLACE_ADD:

>>> dis('i += 1')
  1           0 LOAD_NAME                0 (i)
              2 LOAD_CONST               0 (1)
              4 INPLACE_ADD
              6 STORE_NAME               0 (i)
              8 LOAD_CONST               1 (None)
             10 RETURN_VALUE

There are also several LOAD_NAME or LOAD_CONST. The accumulated costs are much larger than those of the range object iterator directly implemented in C, which makes for loop significantly faster than while loop.

Here is a simple benchmark using perfplot:

import perfplot


def while_loop(lst):
    i = 0
    while i < len(lst):
        i += 1


def for_loop(lst):
    for i in range(len(lst)):
        pass


if __name__ == '__main__':
    perfplot.bench(
        [while_loop, for_loop],
        [2 ** n for n in range(24)],
        [0].__mul__,
        xlabel='len(lst)',
        equality_check=None
    ).show()

Result:

Leetcode Two Sum Question: Difference of For and While Loop

1 Answers