Two Sum
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 <= 104-109 <= nums[i] <= 109-109 <= target <= 109- Only one valid answer exists.
Function Signature (Python):
from typing import List
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
# Your code here
pass
Related Python Concepts
enumerate() Time Complexity Space Complexity Trade-offsHint
Think about how you can efficiently find the "complement" of each number.
- Brute Force: For each number, can you check every other number in the array to see if they sum up to the target? What would be the complexity?
- Optimization: As you iterate through the array, if the current number is
x, you are looking for a numberysuch thatx + y = target. This means you are looking fory = target - x.- Can you store the numbers you've already seen (and their indices) in a way that allows you to quickly check if this complement
yexists? - What data structure provides fast lookups (average O(1) time)?
- Can you store the numbers you've already seen (and their indices) in a way that allows you to quickly check if this complement
Solution Explanation & Interview Strategy
The Goal: We're given a list of numbers (e.g., [2, 7, 11, 15]) and a target sum (e.g., 9). We need to find the positions (indices) of two numbers in the list that add up to this target. For our example, 2 + 7 = 9. Since 2 is at index 0 and 7 is at index 1, the answer is [0, 1].
This is a foundational problem that interviewers use to assess your problem-solving approach and your understanding of basic data structures and their efficiencies.
Approach 1: Brute Force (Nested Loops)
The most straightforward way is to consider every possible pair of numbers in the array and check if their sum equals the target. We can use nested loops for this. The outer loop picks the first number, and the inner loop picks the second number (making sure not to use the same element twice by starting the inner loop from the next index).
from typing import List
class Solution:
def twoSum_brute_force(self, nums: List[int], target: int) -> List[int]:
n = len(nums)
for i in range(n):
for j in range(i + 1, n): # Start j from i+1 to avoid using same element twice
if nums[i] + nums[j] == target:
return [i, j]
return [] # Should not be reached given the problem constraints (exactly one solution)
# Example Usage:
# sol = Solution()
# print(sol.twoSum_brute_force([2, 7, 11, 15], 9)) # Output: [0, 1]
i = 0(nums[0]is 2):j = 1(nums[1]is 7).2 + 7 = 9. Target found! Return[0, 1].
Complexity Analysis:
Time Complexity: O(N2), where N is the number of elements in nums. In the worst case, the inner loop runs N times for each of the N iterations of the outer loop.
Space Complexity: O(1), as we are only using a few variables for iteration and not any extra space proportional to the input size.
Interview Note: This is often the first solution candidates think of. It's important to state it, analyze its complexity, and then discuss how to optimize it.
Approach 2: Using a Hash Map (Dictionary) for One-Pass Solution (Preferred)
We can optimize the search for the second number. For each element x in the array, we need to find if target - x (let's call this complement) exists in the array. A hash map (dictionary in Python) is excellent for this because it provides average O(1) time complexity for lookups.
We can iterate through the array once. For each number, we check if its complement is already in our hash map.
- If the complement is in the map, we've found our pair! We return the current index and the index of the complement (stored in the map).
- If the complement is not in the map, we add the current number and its index to the map, so it can be a potential complement for future numbers.
from typing import List
class Solution:
def twoSum_hash_map(self, nums: List[int], target: int) -> List[int]:
num_map = {} # To store number -> index
for index, num in enumerate(nums):
complement = target - num
if complement in num_map:
# We found the complement that was stored from a previous iteration
return [num_map[complement], index]
# If complement not found, store the current number and its index
# This number might be a complement for a future number in the list
num_map[num] = index
return [] # Should not be reached
# Example Usage:
# sol = Solution()
# print(sol.twoSum_hash_map([2, 7, 11, 15], 9)) # Output: [0, 1]
# print(sol.twoSum_hash_map([3, 2, 4], 6)) # Output: [1, 2]
# print(sol.twoSum_hash_map([3, 3], 6)) # Output: [0, 1]
- Initialize
num_map = {}. index = 0,num = 2:complement = 9 - 2 = 7.- Is
7innum_map? No. - Add
2tonum_map:num_map = {2: 0}.
index = 1,num = 7:complement = 9 - 7 = 2.- Is
2innum_map? Yes,num_map[2]is0. - Return
[num_map[2], index]which is[0, 1].
Complexity Analysis:
Time Complexity: O(N). We iterate through the list containing N elements only once. Each lookup and insertion in the hash map takes O(1) on average.
Space Complexity: O(N). In the worst case, the hash map might store up to N-1 elements if the solution pair is found at the very end (or all elements if no solution was guaranteed, though here one is).
Key Takeaways for Interviews:
- Start Simple (If Time Allows): Briefly mention the brute-force O(N2) solution to show you've considered it.
- Pivot to Optimized: Quickly move to the hash map (dictionary) solution, as this is what interviewers are typically looking for. Explain why it's better (O(N) time).
- Explain the Hash Map Logic: Clearly describe how you use the hash map to store numbers encountered so far and check for complements. The use of
enumerate()is Pythonic for getting both index and value. - Discuss Trade-offs: The hash map solution improves time complexity from O(N2) to O(N) at the cost of O(N) space complexity (versus O(1) space for brute force). This is a common time-space trade-off.
- Clarify Assumptions: The problem statement simplifies things by guaranteeing exactly one solution and not allowing the same element twice. If these assumptions were different (e.g., multiple solutions, or same element allowed if it appears multiple times), you might need to adapt the logic slightly (e.g., for multiple solutions, you might collect all pairs or stop after the first).