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 array of integers nums and a target value, return the indices of the two numbers whose sum equals the target. Each input has exactly one valid pair, and you cannot reuse the same element twice.
Approach 1: Brute Force (O(n^2) time, O(1) space)
The straightforward solution checks every possible pair in the array. Use two nested loops: the outer loop selects the first number, and the inner loop scans the rest of the array to find a number that completes the target sum. For each pair (i, j), check whether nums[i] + nums[j] == target. This approach uses constant extra memory because it only compares values directly. The downside is performance. With n elements, you perform roughly n*(n-1)/2 comparisons, leading to O(n^2) time complexity. Brute force works for small inputs and is often the first step in reasoning about array problems.
Approach 2: Hash Map (O(n) time, O(n) space)
The optimal solution uses a hash table to track previously seen numbers while scanning the array once. For each element nums[i], compute the complement target - nums[i]. If that complement already exists in the hash map, you have found the pair and can return the stored index along with i. If not, store the current value and its index in the map and continue iterating. Hash lookups and insertions run in average O(1) time, so processing the entire array takes O(n). This approach trades memory for speed, storing up to n elements in the map. It’s a classic use of a hash table to convert repeated searches into constant‑time lookups.
The key insight is that instead of searching the array twice for every element, you store previously seen values so the complement check becomes a constant-time operation. This pattern appears in many interview problems where you need fast membership checks inside a single pass.
Recommended for interviews: Interviewers typically expect the hash map solution. Starting with the brute force approach demonstrates you understand the baseline logic and constraints. Moving to the O(n) hash table optimization shows problem‑solving skill and familiarity with common array and lookup patterns. In most real interview settings, candidates who reach the hash map solution quickly and explain the complement logic clearly are demonstrating the intended solution path.
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.
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.
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) | Small arrays or when demonstrating the baseline logic before optimizing |
| Hash Map Lookup | O(n) | O(n) | General case; preferred interview solution with fast complement lookup |
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