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 <= 109O(n2) time complexity?The #1 Two Sum problem asks you to find two indices in an array whose values add up to a given target. Since every element may potentially pair with another, a straightforward idea is to check every possible pair using nested loops. While this brute-force approach is simple to understand, it results in O(n^2) time complexity and can be inefficient for large inputs.
A more optimal strategy uses a hash table. As you iterate through the array, you can store previously seen numbers and their indices in a map. For each number, compute the target - current value and check whether it already exists in the hash table. If it does, you have found the required pair. This technique allows constant-time lookups and reduces the overall complexity to O(n) time.
This pattern—using a hash map for quick complement lookup—is extremely common in coding interviews and helps transform many quadratic problems into linear ones.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Brute Force (Check all pairs) | O(n^2) | O(1) |
| Hash Table Lookup | O(n) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
A really brute force way would be to search for all possible pairs of numbers but that would be too slow. Again, it's best to try out brute force solutions for just for completeness. It is from these brute force solutions that you can come up with optimizations.
So, if we fix one of the numbers, say <code>x</code>, we have to scan the entire array to find the next number <code>y</code> which is <code>value - x</code> where value is the input parameter. Can we change our array somehow so that this search becomes faster?
The second train of thought is, without changing the array, can we use additional space somehow? Like maybe a hash map to speed up the search?
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.
Time Complexity: O(n^2)
Space Complexity: O(1)
1using System;
2
3class Program {
4 static int[] TwoSum(int[] nums, int target) {
5 for (int i = 0; i < nums.Length; i++) {
6 for (int j = i + 1; j < nums.Length; j++) {
7 if (nums[i] + nums[j] == target) {
8 return new int[] { i, j };
9 }
10 }
11 }
12 return new int[] {};
13 }
14
15 static void Main() {
16 int[] nums = { 2, 7, 11, 15 };
17 int target = 9;
18 int[] result = TwoSum(nums, target);
19 Console.WriteLine($"[{result[0]}, {result[1]}]");
20 }
21}The C# implementation involves double for loops to calculate pairwise sums. It searches for two numbers that add up to the target and returns their indices.
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.
Time Complexity: O(n)
Space Complexity: O(n)
1#
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Two Sum is one of the most frequently asked introductory interview questions at companies like Amazon, Google, and Meta. It tests understanding of hash tables, time complexity optimization, and problem-solving patterns.
The optimal approach uses a hash map to store previously seen numbers and their indices while iterating through the array. For each element, you check whether its complement (target minus current value) already exists in the map. This reduces the time complexity to O(n).
Yes, you can solve it using a brute-force approach with two nested loops and no additional data structures. However, this results in O(n^2) time complexity, which is slower than the hash map approach.
A hash table (or hash map) is the best data structure for this problem. It enables constant-time lookups to quickly determine whether the required complement of a number has already appeared in the array.
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.