Two Sum - Solution & Explanation
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.
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 <= 109- Only one valid answer exists.
Follow-up: Can you come up with an algorithm that is less than
O(n2) time complexity?Approach Overview
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.
Approach 1: Brute Force Approach
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.
Complexity
Time Complexity: O(n^2)
Space Complexity: O(1)
Approach 2: Hash Map Approach
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.
Complexity
Time Complexity: O(n)
Space Complexity: O(n)
Approach 3: Hash Table
We can use a hash table d to store each element and its corresponding index.
Traverse the array nums, for the current element nums[i], we first check if target - nums[i] is in the hash table d. If it is in d, it means the target value has been found, and we return the indices of target - nums[i] and i.
Time complexity is O(n), and space complexity is O(n), where n is the length of the array nums.
Code
Complexity Comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2) |
| Hash Map Approach | Time Complexity: O(n) |
| Hash Table | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Two Sum - Leetcode 1 - HashMap - Python • NeetCode • 2,180,712 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Two Sum easy or hard?
How to solve Two Sum in O(n)?
What is the best approach for Two Sum?
What data structure is used in Two Sum?
What is the time complexity of Two Sum?
Two Sum Python or Java solution approach?
Is Two Sum asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Two Sum with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor