1. Two Sum - LeetCode

Problem Description

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.

Example:

• Input: nums = [2,7,11,15], target = 9
• Output: [0,1]
• Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

My Idea

My Initial Idea was to go through the array and check for every element e if target-e is an element in the rest of the array. This, however, results in a time complexity of O(n^2), since for every element we go through the rest of the array and array lookups cost O(n). The optimized version of the algorithm is very similar. In this case we create a dictionary before looping through the elements of the array. Here we check if target-e is a key in the dictionary and if it is, we return the resulting indices. If not, we add e:index of e to the dictionary and continue our loop. The improvement in this version is the use of a dictionary for our lookup, since dict lookups require O(1) time, which reduces our overall algorithm time complexity to O(n)

My solution

# Optimal solution with O(n) Time Complexity and Space Complexity
def twoSum(nums: list[int], target: int) -> list[int]:
        d=dict()
        for i,j in enumerate(nums):
            if (target-j) in d: # O(1) time complexity for dictionary
                return [i,d[target-j]]
            d[j]=i

# Initial solution with Time Complexity: O(n^2) and Space Complexity: O(n)
def twoSumInital(nums: list[int], target: int) -> list[int]:
    for i,j in enumerate(nums):
        if (target-j) in nums[i+1:]:
            return [i,nums.index(target-j,i+1)]