HT

1. Two Sum

Easy
Try it yourself
Problem Statement

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?

Bruteforce solution

  • Use two nested loops to loop the items in nums, with inner loop starting from the current outer loop index plus 1
  • Check if the sum of two numbers at these two indices is equal to the target
  • If yes, return the index
Two-Sum(nums, target):
    for i = 0 -> nums.length - 1:
        for j = i + 1 -> nums.length - 1:
            if nums[i] + nums[j] == target:
                return i, j
    return -1, -1
Two-Sum(nums, target):
    for i = 0 -> nums.length - 1:
        for j = i + 1 -> nums.length - 1:
            if nums[i] + nums[j] == target:
                return i, j
    return -1, -1
  • Time Complexity: O(N^2) with N is the length of the array nums

Hashmap solution

  • Use a hashmap to store key-value pairs as follow:
    • The value of the current element as key
    • Its index as value
  • Use a loop to loop through the items of nums
  • If its complement, which is target - value, is in the hashmap,
    • then we find the pair that sums up to the target
    • else we add the current (value, index) pair to the map
  • Time Complexity: O(N) with N is the length of the array nums
  • Space Complexity: O(N) because we need to store the value-index pairs in a hashmap
Two-Sum(nums, target):
    map = {}
    for index, value in nums:
        complement = target - value
        if complement in map:
            return i, map[complement]
        map[value] = index
    return -1, -1
Two-Sum(nums, target):
    map = {}
    for index, value in nums:
        complement = target - value
        if complement in map:
            return i, map[complement]
        map[value] = index
    return -1, -1