Is the time complexity of the code snippet less than O(n^2)?

Question

I am new to algorithms and data structures. Thus, I joined LeetCode to improve my skills. The first problem is to propose an algorithm whose time complexity is less than O(n^2). I used the code snippet below. The solution was accepted.

def twoSum(nums: List[int], target: int)->List[int]:
    for x in range(len(nums)):
        for y in range(x+1, len(nums)):
            if nums[x] + nums[y] == target:
                return [x, y]
    return [0, 0]

nums = [1,2,3,4]
target = 7
twoSum(nums, target)

But in worst case it iterates N items (indices -> [0,1,2,3]) by (N-1)/2 times (outer index: inner indices -> 0:[1,2,3], 1:[2,3], 2:[3]), seems like O(n^2). Is there any mistake in in my reasoning? Or there is an error on LeetCode?

Answer 1

This is of O(n^2). You can easily calculate the time complexity of your solution which is basically the brute-force way of doing this problem.

In the worst case, you have a Sum of [n, n-1,..., 1] which is equal to n * (n + 1) /2 which is of O(n^2).

Note that such platforms cannot really calculate the time complexity, they just set a time limit on their system which is not accurate in any way.

There exists a simple solution for this problem using Hashmap which gives you a solution of O(n), hope you can figure it out yourself.