Leetcode problem 1 Solution using Python - Two Sum

Problem 

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 O(n2) time complexity?

Solution 1

_ The time complexity of this solution is O(n²) which is pretty..bad. 

_ We are using 2 for loops to solve the problem. 

class Solution:
  def twoSum(self, nums, target):
    for i in range(len(nums)):
      for j in range(i+1, len(nums)):
        if nums[i] + nums[j] == target:
          return [i, j]
s = Solution()
print(s.twoSum([2,7,11,15],9))
print(s.twoSum([3,2,4],6))

Solution 2

In this solution, we iterate over our list of numbers just one and thus the time complexity of the algorithm is O(n) which is way better than the solution implemented previously!

class Solution:
  def twoSum(self, nums, target):
    values = {}
    for idx, value in enumerate(nums):
      if target-value in values:
        return [values[target - value], idx]
      else:
        values[value] = idx
s = Solution()
print(s.twoSum([2,7,11,15],9))
print(s.twoSum([3,2,4],6))

Thanks for reading this article. Keep learning