1. Two Sum
Problem Description
In this problem, we have an array of integers called nums
and a target integer called target
. Our task is to find two distinct numbers within the array that when added together, equal the target
. One important rule is that we cannot use the same element from the array twice in our sum. The output will be the indices (positions in the array) of these two numbers, and it does not matter in which order we provide these indices. Each valid input to the problem is guaranteed to have exactly one solution.
Intuition
To solve this problem efficiently, we avoid the brute force approach of trying every possible pair of numbers to see if they add up to the target. Instead, we employ a hash table (dictionary in Python), which offers fast lookup times that average out to O(1) complexity. The basic idea is to iterate through the list once, and for each number, we check if the number required to reach the target (target - current_number
) has already been seen in the array. If it has, then we have found the two numbers whose sum is equal to the target.
As we iterate through the nums
array, we keep track of each number and its index in the hash table. So for each number x
, we calculate y
which is the difference between target
and x
. If y
is found in the hash table, it means we have previously processed another number such that x + y = target
. In that case, we immediately return the pair of indices: one for the current number x
, and one for the previously stored number y
. If y
is not found in the hash table, we store x
along with its index in the hash table and move on to the next element in the array. This approach only requires a single pass through the array, making the solution efficient and elegant.
Solution Approach
The solution provided uses a hash table to map each element's value to its index in the array. This allows for constant-time look-ups which are critical for efficiency. The algorithm proceeds as follows:
- Initialize an empty hash table (dictionary in Python dialect), we'll call it
m
. - Iterate over the
nums
array, enumerating both the valuex
and its indexi
. Enumeration provides a convenient way of getting both the value and the index without additional overhead. - For every value
x
, calculate its complementy
by subtractingx
fromtarget
(y = target - x
). - Check if
y
is present as a key in the hash table. If it is found, it means we had already seen the necessary pair earlier in the array. We then retrievem[y]
, which is the index ofy
we had stored, and return a list containing the indices ofy
andx
([m[y], i]
). This satisfies the requirement as their sum is equal to thetarget
. - If
y
is not in the hash table, add the current valuex
along with its indexi
to the hash table (m[x] = i
). This storesx
for future reference if we later come across its complementy
.
By only traversing the array once, the overall time complexity is O(n)
, where n
is the number of elements in nums
. The space complexity is also O(n)
as in the worst case, we could potentially store all elements in the hash table before finding a match.
Here's the provided solution approach step in the code:
1class Solution:
2 def twoSum(self, nums: List[int], target: int) -> List[int]:
3 m = {} # Step 1: Initialize the hash table
4 for i, x in enumerate(nums): # Step 2: Enumerate through nums
5 y = target - x # Step 3: Calculate complement y
6 if y in m: # Step 4: Check if y is present in the hash table
7 return [m[y], i] # Return the indices of the two elements adding up to target
8 m[x] = i # Step 5: Store x with its index in hash table for future reference
The strength of this approach is that it smartly utilizes the hash table to avoid nested loops and thus reducing the time complexity. The algorithm is linear time as it eliminates the need to examine every possible pair by keeping a record of what is needed to reach the target with the current number.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's work through a small example to illustrate the solution approach.
Suppose our input array nums
is [2, 7, 11, 15]
and the target
is 9
.
Following the solution steps:
-
Initialize an empty hash table (dictionary), which we'll name
m
. -
Now we start iterating over the
nums
array:-
First iteration (i = 0):
- We take the first element
nums[0]
which is2
. - Calculate its complement
y = target - nums[0]
, which gives usy = 9 - 2 = 7
. - Check if
7
is present in the hash tablem
. It isn't, sincem
is empty. - Store the current value
2
along with its index0
in the hash table:m[2] = 0
.
- We take the first element
-
Second iteration (i = 1):
- Take the next element
nums[1]
, which is7
. - Calculate its complement
y = target - nums[1]
, which gives usy = 9 - 7 = 2
. - Check if
2
is in the hash tablem
. Yes, it is! The complement2
was stored during the first iteration. - Since the complement is found, we retrieve
m[2]
which is0
, the index of the complement2
. This gives us the indices[0, 1]
.
- Take the next element
-
The sum of the numbers at these indices (nums[0] + nums[1]
) equals the target
(2 + 7 = 9). As expected, the original problem statement guarantees that there is exactly one solution, so the problem is now solved with the output [0, 1]
.
By using this hash table approach, we efficiently found the two numbers that add up to the target in a single pass through the array, thereby using O(n)
time complexity instead of O(n^2)
which would result from using a brute force approach with nested loops.
Solution Implementation
1from typing import List # Import List for type annotation
2
3class Solution:
4 def twoSum(self, nums: List[int], target: int) -> List[int]:
5 # Create a dictionary to store numbers and their indices
6 index_map = {}
7 # Enumerate through the list of numbers
8 for index, number in enumerate(nums):
9 # Calculate the complement of the current number
10 complement = target - number
11 # If complement is in the index_map, a solution is found
12 if complement in index_map:
13 # Return the indices of the two numbers
14 return [index_map[complement], index]
15 # Otherwise, add the current number and its index to the index_map
16 index_map[number] = index
17 # If no solution is found, this return will not be reached due to guaranteed solution.
18
1import java.util.Map;
2import java.util.HashMap;
3
4class Solution {
5 public int[] twoSum(int[] nums, int target) {
6 // Create a hashmap to store the value and its index
7 Map<Integer, Integer> indexMap = new HashMap<>();
8
9 // Iterate over the array elements
10 for (int i = 0; i < nums.length; i++) {
11 int current = nums[i]; // Current element value
12 int complement = target - current; // The complement which, when added to 'current', equals 'target'
13
14 // Check if the complement is already in the map
15 if (indexMap.containsKey(complement)) {
16 // If complement is found, return the indices of the two numbers
17 return new int[] {indexMap.get(complement), i};
18 }
19
20 // Store the current value and its index in the map
21 indexMap.put(current, i);
22 }
23 // Note: The problem statement guarantees that there will always be exactly one solution,
24 // so no need to return null or throw an exception here.
25 throw new IllegalArgumentException("No two sum solution found");
26 }
27}
28
1#include <vector>
2#include <unordered_map>
3
4class Solution {
5public:
6 // Function to find the indices of the two numbers that add up to a specific target.
7 std::vector<int> twoSum(std::vector<int>& nums, int target) {
8 // Create a hash map to store the value and its index.
9 std::unordered_map<int, int> num_to_index;
10
11 // Iterate through each number in the vector.
12 for (int i = 0; i < nums.size(); ++i) {
13 int current_num = nums[i]; // Current number in the iteration.
14 int complement = target - current_num; // Find the complement of the current number.
15
16 // If the complement is found in the map, return the pair of indices.
17 if (num_to_index.count(complement)) {
18 return {num_to_index[complement], i};
19 }
20
21 // If complement is not found, add the current number and its index to the map.
22 num_to_index[current_num] = i;
23 }
24
25 // In case no solution is found (this part is unreachable if input is guaranteed to have one solution as stated in the problem).
26 return {}; // Return an empty vector.
27 }
28};
29
1// Define the function signature with input types and return type
2function twoSum(nums: number[], target: number): number[] {
3 // Initialize a map to store the numbers and their indices
4 const numIndexMap = new Map<number, number>();
5
6 for (let i = 0; i < nums.length; i++) {
7 const currentNum = nums[i]; // The current number in the array
8 const complement = target - currentNum; // The number that complements the current number to reach the target
9
10 // Check if the complement is already in the map
11 if (numIndexMap.has(complement)) {
12 // If complement is found, return its index along with the current index
13 return [numIndexMap.get(complement)!, i];
14 }
15
16 // If complement is not found, add current number and its index to the map
17 numIndexMap.set(currentNum, i);
18 }
19
20 // Since the problem guarantees exactly one solution, the loop should never finish without returning.
21 // If no solution is found (which violates the problem's constraints), throw an error.
22 throw new Error('No two sum solution exists');
23}
24
25// The function `twoSum` can now be used as per its signature with TypeScript type checking.
26
Time and Space Complexity
The time complexity of the code is O(n)
, where n
is the length of the array nums
. This is because the code loops through each element in nums
exactly once, and each operation within the loop—including checking if an element exists in the map m
and adding an element to m
—is O(1)
.
The space complexity of the code is also O(n)
, since in the worst case, the code may insert each element of the array nums
into the map m
. Therefore, the space used by the map m
grows linearly with the number of elements in nums
.
Learn more about how to find time and space complexity quickly using problem constraints.
The three-steps of Depth First Search are:
- Identify states;
- Draw the state-space tree;
- DFS on the state-space tree.
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.
reviewed