Two Sum (Leetcode #1)

Question:

Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to the target.

Constraints:

• Each input would have exactly one solution.

• The same element cannot be used twice.

Examples:

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]

Answer:

Brute Force Approach:

One way to solve this problem is by using a brute force approach. We can find the target and the index of the pair by trying every combination of numbers in nums. However, this approach results in a time complexity of O(N^2) because we have to go through every combination and a space complexity of O(1).

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

Improvement: Using Hashmap

Time Complexity of using Hashmap:

• Insertion (put):

  • Average Case: O(1)

  • Worst Case: O(n)

• Lookup (get):

  • Average Case: O(1)

  • Worst Case: O(n)

Algorithm:

1. Initialize an empty dictionary seen to store numbers and their indices.

2. Iterate through the list nums using indices i.

3. Check if target - nums[i] exists in seen.

   • If found, return the indices of the two numbers that add up to target.

   • If not found, store nums[i] in seen with its index.

4. If no such pair is found, it means there's no solution,

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        seen = {}
        for i in range(len(nums)):
            if target - nums[i] in seen:
                return [seen[target - nums[i]], i]
            else:
                seen[nums[i]] = i

Time Complexity

O(N) because we go through the list ounce

Space Complexity

O(N) because we create a hashmap of size N