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 the 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 develop an algorithm that is less than O(n2) time complexity?

Brute Force

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

Complexity

Time

𝑂( 𝑛² )

Since it is 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 the compliment is in the hashmap return the index of the compliment in the hashmap and the current index in the loop

• else add the 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 no two numbers 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