1-two-sum

Try it on leetcode

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]
Output: 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(Python)

class Solution:
    # Input: nums array
    # Output: return the index of two numbers in a Tuple
    #
    # Assumption: only one solution exists
    # Constraints:
    #   1.-10^9 <= nums[i],target <= 10^9
    #   2.2<=nums.length<= 10^4
    #
    #
    # BruteForce: Do exactly what was given in the problems
    #  run two loops to find the numbers that sums to target and
    #   return their target
    #
    # Time Complexity:O(n^2)
    # Space Complexity:O(1)
    #
    # Optimised Approach: we can skip the inside second loop
    # via caching it in the memory i.e a Hashmap
    #
    # since our condition is num1 + num2 = target
    # which implies
    #  num2 = target - num1
    # so if we cache num1 in the hashmap
    # and then later if we found target - num1
    # then num1 and num2 are our required answer
    #
    # Time Complexity:O(n)
    # on average Time Compleixty is 2n so at worst caseit's O(n)
    #
    # Space Complexity:O(n)
    #   extra space for hashmap of size n here we trade extra space for speed
    #
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = {}  # Hashmap to store num
        n = len(nums)

        for i in range(n):
            num1 = nums[i]
            num2 = target - num1

            if num2 in hashmap:  # if num2 in found we got the match
                return [i, hashmap[num2]]
            hashmap[num1] = i