Two Sum

Problem Statement

In this problem, we are tasked with solving the Two Sum challenge.

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

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]
Explanation: nums[1] + nums[2] == 6

Input: nums = [3,2,4], target = 6
Output: [1,2]
Explanation: nums[1] + nums[2] == 6

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

• 2 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9
• Only one valid answer exists

Follow-up:

Can you come up with an algorithm that is less than O(n²) time complexity?

Approach

Initial Thoughts

The brute force approach would check every pair of numbers (O(n²)), but we can optimize using a hash map. The key insight is: for each number, we can calculate what its complement needs to be (target - current_number), then check if we’ve seen that complement before.

Strategy

Use a hash map to store numbers we’ve seen along with their indices. As we iterate through the array, for each number:

1. Calculate the complement needed to reach the target
2. Check if that complement exists in our hash map
3. If yes, we found our pair – return both indices
4. If no, store current number and its index for future lookups

Key Insights

• Hash map provides O(1) lookup time for checking if complement exists
• We only need one pass through the array
• Store value → index mapping (not index → value)
• Check for complement before adding current number to map (handles edge cases)
• The problem guarantees exactly one solution exists (no need to handle multiple solutions)
• We can’t use the same element twice, but two different elements can have the same value

Algorithm Steps

1. Create an empty hash map seen to store {value: index} pairs
2. Iterate through array with index i from 0 to n-1:
   • Calculate complement = target - nums[i]
   • Check if complement exists in seen:
     • If yes: Return [seen[complement], i] (found the pair!)
     • If no: Continue to next step
   • Store current number in map: seen[nums[i]] = i
3. (We’ll always find a solution per problem guarantee)

Complexity Analysis

Time Complexity: O(n) – Single pass through the array. Hash map operations (lookup and insert) are O(1) average case.

Space Complexity: O(n) – In worst case, we store n-1 elements in the hash map before finding the solution on the last element.

Code

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen = {}  # Maps value -> index</em>
        
        for i in range(len(nums)):
            complement = target - nums[i]
            
            # Check if complement exists in our map</em>
            if complement in seen:
                return [seen[complement], i]
            
            # Store current number and its index</em>
            seen[nums[i]] = i

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen = {}  # Maps value -> index</em>
        
        for i in range(len(nums)):
            complement = target - nums[i]
            
            # Check if complement exists in our map</em>
            if complement in seen:
                return [seen[complement], i]
            
            # Store current number and its index</em>
            seen[nums[i]] = i

Alternative (More Pythonic):

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen = {}
        
        for i, num in enumerate(nums):
            complement = target - num
            if complement in seen:
                return [seen[complement], i]
            seen[num] = i

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen = {}
        
        for i, num in enumerate(nums):
            complement = target - num
            if complement in seen:
                return [seen[complement], i]
            seen[num] = i

Code Walkthrough

Line 3: Initialize empty hash map seen to store {value: index} mappings

Line 5: Loop through array with index i

Line 6: Calculate the complement – the value we need to find to reach our target

• Example: If target = 9 and nums[i] = 2, then complement = 7

Line 9: Check if this complement already exists in our hash map

• This is the key optimization: O(1) lookup instead of O(n) search

Line 10: Found a match! Return the indices

• seen[complement] gives us the index where we saw the complement
• i is the current index
• Order doesn’t matter per problem statement

Line 13: No match yet, so store current number with its index

• This makes it available for future complement checks
• Note: We add after checking, which prevents using same element twice

Edge Cases to Consider

1. Minimum size array: nums = [1, 2], target = 3 → [0, 1]
2. Duplicate values:nums = [3, 3], target = 6 → [0, 1]
   • Works correctly because we check before adding
3. Negative numbers: nums = [-1, -2, -3, -4, -5], target = -8 → valid
4. Zero in array: nums = [0, 4, 3, 0], target = 0 → [0, 3]
5. Target is zero: nums = [-3, 3], target = 0 → [0, 1]
6. Large numbers: Values up to 10^9
7. Solution at start: nums = [2, 7, 11, 15], target = 9 → [0, 1]
8. Solution at end: nums = [11, 15, 2, 7], target = 9 → [2, 3]
9. Same number appears multiple times: nums = [2, 5, 5, 11], target = 10 → [1, 2]

Similar Problems

• LC 1: Two Sum (this problem)
• LC 167: Two Sum II – Input Array Is Sorted (use two pointers)
• LC 15: 3Sum
• LC 18: 4Sum
• LC 454: 4Sum II
• LC 653: Two Sum IV – BST
• LC 1099: Two Sum Less Than K
• LC 170: Two Sum III – Data structure design
• LC 653: Two Sum IV – BST

Personal Notes

• This is THE most famous LeetCode problem – must know it cold for interviews
• Classic example of trading space for time (O(n) space to achieve O(n) time)
• Why we check before adding to map:
  • Prevents using the same element twice
  • Example: nums = [3, 2, 4], target = 6 – if we add before checking, nums[0]=3 would match with itself when we later look for 3 again
• Common beginner mistakes:
  1. Adding to map before checking (can use same element twice)
  2. Storing index → value instead of value → index
  3. Trying to sort the array (loses original indices)
  4. Using two nested loops (O(n²) instead of O(n))
• The variable name complement is better than diff or needed – more descriptive
• This pattern (hash map for O(1) lookups) is extremely common in array problems
• Interview tip: Mention the brute force O(n²) approach first, then optimize
• The problem guarantees exactly one solution, so no need to handle:
  • No solution case
  • Multiple solutions case
• For sorted array variant (LC 167), two-pointer approach is better (O(1) space)