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].
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 <= 109Follow-up: Can you come up with an algorithm that is less than
O(n2) time complexity?Problem Overview: Given an integer array nums and a target value, return the indices of two numbers whose sum equals the target. Each input has exactly one valid pair, and you cannot reuse the same element twice. The challenge is finding that pair efficiently without checking every possible combination.
Approach 1: Brute Force (O(n^2) time, O(1) space)
The most direct solution checks every possible pair of numbers. Use two nested loops: the outer loop picks the first number and the inner loop scans the rest of the array for a second number that satisfies nums[i] + nums[j] == target. Once the pair is found, return their indices. This approach works for any array and requires no extra data structures, so the space complexity stays O(1). The downside is the time complexity: with n elements, you potentially evaluate n(n-1)/2 pairs, resulting in O(n^2) time. It’s useful as a baseline during interviews because it demonstrates clear reasoning before optimizing.
Approach 2: Hash Map (O(n) time, O(n) space)
The optimal solution uses a hash table to track numbers you have already seen while scanning the array once. For each element nums[i], compute its complement target - nums[i]. Check if that complement already exists in the hash map. If it does, you found the required pair and can immediately return the stored index and the current index. If it does not, store the current number and its index in the map and continue iterating.
The key insight is that instead of searching the array repeatedly, the hash map allows constant-time lookups. Each iteration performs a hash lookup and possibly an insertion, both averaging O(1). Because the array is scanned once, the total time complexity becomes O(n). The tradeoff is extra memory: the map may store up to n elements, leading to O(n) space complexity.
This technique is a classic pattern when solving array problems involving complements, frequencies, or fast membership checks. Variants of this idea appear in many interview questions such as Two Sum II, Subarray Sum Equals K, and other problems involving prefix sums and lookups.
Recommended for interviews: Interviewers usually expect the hash map solution because it reduces the runtime from O(n^2) to O(n). Start by explaining the brute force approach to show you understand the problem space, then optimize using a hash map. Demonstrating that transition—from pair comparison to constant-time lookups—shows strong algorithmic thinking.
This approach uses a simple brute force algorithm, which consists of checking each pair of numbers to see if they add up to the target. Although this is straightforward, it is not the most efficient method. We loop through each number in the array using two nested loops, effectively trying all combinations of two numbers.
The C solution uses two nested for loops to iterate through the array. The outer loop selects the first element, and the inner loop checks every subsequent element for a pair whose sum equals the target. If such a pair is found, their indices are printed.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2)
Space Complexity: O(1)
This efficient approach utilizes a hash map to store the difference between the target and the current element (called 'complement') as the key and the element's index as the value. As we iterate through the array, we check if the current element is a key in the hash map, which indicates that its complement was seen earlier, thus allowing us to retrieve the correct indices quickly.
In this C code, we use a basic hash table to store indices. As we traverse the array, we calculate complements and check if they exist in the hash table. If a complement is found, it means we have already seen the required number, and we can quickly return the indices using the hash map.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n)
Space Complexity: O(n)
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2) |
| Hash Map Approach | Time Complexity: O(n) |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force (Nested Loops) | O(n^2) | O(1) | Baseline approach or when input size is very small and simplicity is preferred |
| Hash Map Lookup | O(n) | O(n) | General case; best choice when fast lookups are needed for complement values |
Two Sum - Leetcode 1 - HashMap - Python • NeetCode • 1,640,483 views views
Watch 9 more video solutions →Practice Two Sum with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor