Two sum

This article will highlight two approaches the brute force and the efficient approach

Question

Leetcode link -> https://leetcode.com/problems/two-sum/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 1

Input: nums = [2,7,11,15], target = 9
Output: [0,1]

Explanation: Because nums[0] + nums[1] == 9, 
we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]


Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]


Constraints:

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than 𝑂( 𝑛 ² ) time complexity?

Brute Force

Use double for loop, for each value add the values and check if they equal the target

Complexity

Time

𝑂( 𝑛 ² )

Since its a double for loop, each element is paired with every other element exactly once

Space

𝑂( 1 )

This approach does not use any extra data structures that grow with the size of the input.

which means it is constant space.

Code

class Solution:
    for i in range(len(nums)):
      for j in range(i+1, len(nums)):
         if(nums[i] + nums[j] == target):
            return [i,j]
    return None

Efficient approach

Use a hashmap

• Use one for loop and enumerate list
• target minus each element
• if compliment in hashmap return the index of the compliment in the hashmap and the current index in loop
• else add element as key and index as value

Complexity

Time

𝑂(𝑛)

Because we traverse the list once, and dictionary operations (insertion and lookup) are O( 1 ) on average

Space

𝑂(𝑛)

In the worst case, if there are no two numbers that sum up to the target, every element will be stored in the hash map.
Therefore, the space complexity is 𝑂(𝑛) where 𝑛 is the number of elements in the list.

Code

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        two_hash = {}
        for i, num in enumerate(nums):
            compliment = target - num
            if compliment in two_hash:
                return [two_hash[compliment], i]
            two_hash[num] = i
        return None