Two Sum Problem: Explanation and Solutions
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.
Example 1:
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: nums[0] + nums[1] = 2 + 7 = 9
Example 2:
Input: nums = [3, 2, 4], target = 6
Output: [1, 2]
Constraints:
Each input has exactly one solution.
You cannot use the same element twice.
You can return the answer in any order.
Approach 1: Brute Force (Nested Loops)
Time Complexity: O(n^2)
Space Complexity: O(1)
This approach checks every possible pair to see if their sum equals the target.
def two_sum(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]
return []
Approach 2: Using HashMap (Optimal Solution)
Time Complexity: O(n)
Space Complexity: O(n)
A hashmap (dictionary) stores previously visited elements, allowing for constant-time
lookups.
def two_sum(nums, target):
num_map = {} # Dictionary to store numbers and their indices
for i, num in enumerate(nums):
complement = target - num
if complement in num_map:
return [num_map[complement], i]
num_map[num] = i # Store the number with its index
return []
🔹 Why is this efficient?
Instead of looping through all pairs, we use a dictionary for quick lookups.
We traverse the array only once (linear time complexity).
Approach 3: Two-Pointer (For Sorted Array)
Time Complexity: O(n log n) (if sorting) or O(n) (if already sorted)
Space Complexity: O(1)
This approach works if the array is sorted.
def two_sum_sorted(nums, target):
nums = sorted(enumerate(nums), key=lambda x: x[1]) # Sort with
original indices
left, right = 0, len(nums) - 1
while left < right:
curr_sum = nums[left][1] + nums[right][1]
if curr_sum == target:
return [nums[left][0], nums[right][0]]
elif curr_sum < target:
left += 1
else:
right -= 1
return []
⚠ Caution: If the array is unsorted, sorting adds an O(n log n) overhead.
Comparison of Approaches
Approach Time Complexity Space Complexity Best for?
Brute Force O(n^2) O(1) Small datasets
HashMap O(n) O(n) Best overall (fastest)
Two-Pointer O(n log n) O(1) Sorted arrays
Follow-Up Questions
1. What if the array contains duplicate numbers?
o The hash table approach still works fine because we store indices.
2. What if we need to return all unique pairs?
o Use a set to store pairs and avoid duplicates.
3. What if we need the elements instead of indices?
o Modify the function to return [nums[i], nums[j]].
This document provides a structured explanation of the Two Sum problem with different
approaches, their complexities, and best-use cases. Would you like implementations in other
languages (C++, Java, etc.) or variations like "Three Sum" or "K Sum"?