Watch 10 video solutions for Two Sum, a easy level problem involving Array, Hash Table. This walkthrough by NeetCode has 2,053,802 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |