1. Two Sum

Easy

JuniorArrayHash Table

Answered: Dec 3, 2022

Problem 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.

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]

Constraints

2 <= nums.length <= 10⁴
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= target <= 10⁹
Only one valid answer exists.

Follow-up

Can you come up with an algorithm that is less than $O(n^{2})$ time complexity?

💡 Hints (3)

Solutions

Complexity Analysis

Time Complexity:

O (n^{2})

We have two nested loops, each iterating through the array of length n, resulting in $O(n^{2})$ time complexity.

Space Complexity:

O (1)

We only use a constant amount of extra space for the indices and temporary variables.

The brute force approach is straightforward: we check every possible pair of numbers in the array to see if they add up to the target. We use two nested loops, where the outer loop picks the first number and the inner loop checks for the second number that complements it to reach the target.

Complexity Analysis

Time Complexity:

O (n^{2})

The in operator (or includes method) checks for the presence of an element in the list, which takes $O(n)$ time. Since we do this for each of the n elements, the overall time complexity is $O(n^{2})$ .

Space Complexity:

O (n)

We store at most n elements in the list.

In this approach, we maintain a list of numbers we have seen so far. For each number in the array, we calculate its complement (the number needed to reach the target) and check if it exists in our list. If it does, we return the indices of the complement and the current number. If it doesn't, we add the current number to the list for future reference.

Complexity Analysis

Time Complexity:

O (n)

We iterate through the array once, and each lookup in the hash map is $O(1)$ on average.

Space Complexity:

O (n)

We store at most n elements in the hash map.

In this approach, we use a hash map (dictionary in Python, Map in JavaScript) to store numbers we have already seen along with their indices. For each number in the array, we calculate its complement (the number needed to reach the target) and check if this complement is already in our hash map. If it is, we return the indices of the complement and the current number. If not, we add the current number and its index to the hash map.

Complexity Analysis

Time Complexity:

O (n lo g n)

Sorting the list takes $O(n \log n)$ time, and the two-pointer traversal takes $O(n)$ time, resulting in an overall time complexity of $O(n \log n)$ .

Space Complexity:

O (n)

We store n pairs in the array, so the space complexity is $O(n)$ .

In this approach, we first create a list of pairs where each pair contains a number from the input array and its corresponding index. We then sort this list based on the numbers. After sorting, we can use the two-pointer technique to find the two numbers that add up to the target. We initialize one pointer at the beginning of the list and another at the end. We calculate the sum of the numbers at these pointers and compare it to the target. If the sum is equal to the target, we return their indices. If the sum is less than the target, we move the left pointer to the right to increase the sum. If the sum is greater than the target, we move the right pointer to the left to decrease the sum.

Conclusion

Approach	Time Complexity	Space Complexity	Advantages	Disadvantages
Brute Force	$O(n^{2})$	$O(1)$	Simple to understand; No extra space needed	⚠️ Very slow for large inputs
Using a List	$O(n^{2})$	$O(n)$	Cleaner intent than brute force	⚠️ Still $O(n^{2})$ due to linear search; Uses extra space
Using a Hash Map	$O(n)$	$O(n)$	Optimal time complexity; Single pass through array	Requires extra space for hash map
Sorting and Two Pointers	$O(n \log n)$	$O(n)$	Demonstrates two-pointer technique; Good sorting practice	Slower than hash map; Requires sorting step

The recommended approach for this problem is Solution 3: Using a Hash Map. It achieves the best time complexity of $O(n)$ by trading a small amount of extra space for a hash map that enables $O(1)$ lookups. This eliminates the need for nested loops or sorting, making it the most efficient approach for this problem.

Solutions

lines
1class Solution:
  def twoSum(self, nums: List[int], target: int) -> List[int]:
      for i in range(len(nums)):
          # Calculate the complement of the current number
          for j in range(i + 1, len(nums)):
              if nums[j] == target - nums[i]:
                  return [i, j]

Complexity Analysis

Time Complexity:

O (n^{2})

We have two nested loops, each iterating through the array of length n, resulting in $O(n^{2})$ time complexity.

Space Complexity:

O (1)

We only use a constant amount of extra space for the indices and temporary variables.

lines
1class Solution:
  def twoSum(self, nums: List[int], target: int) -> List[int]:
      list = []
4
      for i in range(len(nums)):
          diff = target - nums[i]
7
          # check if the diff is in the list, if it is, return the index of the diff and the current index
          if diff in list:
              return [list.index(diff), i]
          else:
              list.append(nums[i])

Complexity Analysis

Time Complexity:

O (n^{2})

Space Complexity:

O (n)

We store at most n elements in the list.

12 lines
1class Solution:
2    def twoSum(self, nums: List[int], target: int) -> List[int]:
3        dict = {}
4
5        for i, num in enumerate(nums):
6            neededValue = target - num
7
8            # check if the needed value is already in the dict
9            if neededValue in dict and dict[neededValue] != i:
10                return [i, dict[neededValue]]
11
12            dict[num] = i

Complexity Analysis

Time Complexity:

O (n)

We iterate through the array once, and each lookup in the hash map is $O(1)$ on average.

Space Complexity:

O (n)

We store at most n elements in the hash map.

lines
1class Solution:
  def twoSum(self, nums: List[int], target: int) -> List[int]:
      list = []
4
      # store the number and its index in the list
      for i, num in enumerate(nums):
          list.append([num, i])
8
      list.sort()
10
      left = 0
      right = len(list) - 1
13
      while left < right:
          sum = list[left][0] + list[right][0]
16
          if sum == target:
              return [list[left][1], list[right][1]]
          elif sum < target: # if the sum is less than the target, we need to increase the sum by moving the left pointer to the right
              left += 1
          else: # if the sum is greater than the target, we need to decrease the sum by moving the right pointer to the left
              right -= 1
23
      return []

Complexity Analysis

Time Complexity:

O (n lo g n)

Sorting the list takes $O(n \log n)$ time, and the two-pointer traversal takes $O(n)$ time, resulting in an overall time complexity of $O(n \log n)$ .

Space Complexity:

O (n)

We store n pairs in the array, so the space complexity is $O(n)$ .

Conclusion

Approach	Time Complexity	Space Complexity	Advantages	Disadvantages
Brute Force	$O(n^{2})$	$O(1)$	Simple to understand; No extra space needed	⚠️ Very slow for large inputs
Using a List	$O(n^{2})$	$O(n)$	Cleaner intent than brute force	⚠️ Still $O(n^{2})$ due to linear search; Uses extra space
Using a Hash Map	$O(n)$	$O(n)$	Optimal time complexity; Single pass through array	Requires extra space for hash map
Sorting and Two Pointers	$O(n \log n)$	$O(n)$	Demonstrates two-pointer technique; Good sorting practice	Slower than hash map; Requires sorting step

Problem Description

Examples

Example 1

Example 2

Example 3

Constraints

Follow-up

💡 Hints (3)

Solutions

Solution 1: Brute Force

Complexity Analysis

Explanation

Solution 2: Using a List to Store Seen Numbers

Complexity Analysis

Explanation

Solution 3: Using a Hash Map

Complexity Analysis

Explanation

Solution 4: Sorting and Two Pointers

Complexity Analysis

Explanation

Conclusion

Problem Description

Examples

Example 1

Example 2

Example 3

Constraints

Follow-up

💡 Hints (3)

Solutions

Solution 1: Brute Force

Complexity Analysis

Explanation

Solution 2: Using a List to Store Seen Numbers

Complexity Analysis

Explanation

Solution 3: Using a Hash Map

Complexity Analysis

Explanation

Solution 4: Sorting and Two Pointers

Complexity Analysis

Explanation

Conclusion