How to Solve Two Sum on LeetCode
The Two Sum problem is one of the most famous LeetCode questions, testing your ability to use hashing and array indexing for efficient pair finding.
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. Assume each input has exactly one solution, and you may not use the same element twice.
Example:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Why This Problem Matters for Interviews
This problem:
- Checks your grasp of hash maps for constant-time lookups
- Highlights time-space trade-offs in array processing
- Appears as a subroutine in more complex interview questions
Approaches to Two Sum
1. Brute Force (Naive)
Check every pair of elements.
Time Complexity: O(n^2)
Space Complexity: O(1)
def twoSum(nums: list[int], target: int) -> list[int]:
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
2. Hash Map (Optimal)
Store seen numbers and their indices for O(1) complement lookup.
Time Complexity: O(n)
Space Complexity: O(n)
def twoSum(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
Key Interview Talking Points
- Why a hash map gives O(n) time vs brute force O(n^2)
- Handling duplicate numbers and not using same element twice
- Discuss trade-offs if only outputting the pair, not indices
- Edge cases: negative numbers, no solution, multiple pairs
Big O Complexity Recap
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Brute Force | O(n^2) | O(1) |
| Hash Map | O(n) | O(n) |
Pro Interview Tips
- Walk through hash map population and lookups.
- Mention what changes if you want all pairs, not just one.
- Practice with test cases