Two Sum Solution In C++/Java/Python/JS
Problem Description
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 will have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Examples:
Input : nums = [11, 2, 15, 7], target = 9
Output : [1, 3]
Explanation : Because nums[1] + nums[3] == 9, we return [1, 3].
Input : nums = [3, 3], target = 6
Output : [0, 1]
Explanation : Because nums[0] + nums[1] == 6, we return [0, 1].
Constraints:
- 2 ≤ nums.length ≤ 10^4
- -10^9 ≤ nums[i] ≤ 10^9
- -10^9 ≤ target ≤ 10^9
- Only one valid answer exist
The problem is simple yet interesting we need to find two numbers in the array that add up to a given target. Since there’s only one valid pair, our goal is to figure out which two numbers they are and return their indices.
Brute Force Approach
Intuition
To solve this problem, we need to identify two numbers in the array whose sum equals the target and return their indices. The simplest way to approach this is to systematically check all possible pairs in the array
The idea is simple—if we want to find two numbers that add up to a target, we just need to systematically compare each number in the array with every other number to see if their sum equals the target.
For example, pick the first number in the array and then compare it with every other number in the array. If their sum matches the target, we return their indices. If not, we move to the next number and repeat the process.
This method ensures that no possible pair is missed because every number is compared with every other number in the array. By following this systematic process, we can confidently say that we will find the correct pair whose sum matches the target. This approach guarantees that the solution is accurate, as it leaves no combination unchecked.
Approach
Step 1: Initialize the Outer Loop
Start by creating an outer loop that iterates through the array. This loop picks the first number in each potential pair. The loop will go from the first element to the second-to-last element since each number needs to be paired with another.
Step 2: Initialize the Inner Loop
For each number selected by the outer loop, use an inner loop to iterate through the remaining numbers in the array. The inner loop starts from the next index (i + 1) to avoid pairing a number with itself and to prevent checking the same pair twice.
Step 3: Check the Pair’s Sum
Within the inner loop, add the two numbers from the current indices of the outer and inner loops. Compare the sum of these two numbers with the target value.
Step 4: Return the Indices if the Pair Matches
If the sum equals the target, return the indices of the two numbers (i and j) as the solution.
Dry run
Input: nums = [11, 7, 15, 2], target = 9
Output: [1, 3]
Step 1: Outer Loop (i = 0)
- Pick the first number: nums[0] = 11.
Step 2: Inner Loop
- Compare 11 + nums[1] = 11 + 7 = 18 (not equal to target).
- Compare 11 + nums[2] = 11 + 15 = 26 (not equal to target).
- Compare 11 + nums[3] = 11 + 2 = 13 (not equal to target).
- No match found in this iteration.
Step 3: Outer Loop (i = 1)
- Pick the second number: nums[1] = 7.
Step 4: Inner Loop
- Compare 7 + nums[2] = 7 + 15 = 22 (not equal to target).
- Compare 7 + nums[3] = 7 + 2 = 9 (this equals the target).
Step 5: Match Found
- Return indices [1, 3].
Final Output: [1, 3]
Code for All Languages
C++
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
// Function to find two indices such that their sum equals the target
vector<int> twoSum(vector<int>& nums, int target) {
// Outer loop to iterate through the array
for (int i = 0; i < nums.size(); i++) {
// Inner loop to find the second number that forms the pair
for (int j = i + 1; j < nums.size(); j++) {
// Check if the sum of the two numbers equals the target
if (nums[i] + nums[j] == target) {
// Return the indices of the pair
return {i, j};
}
}
}
// Return empty vector if no solution is found (shouldn't happen as per problem constraints)
return {};
}
};
int main() {
// Input the size of the array
int n, target;
cin >> n;
// Input the array elements
vector<int> nums(n);
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
// Input the target
cin >> target;
// Create an instance of the Solution class
Solution solution;
// Call the function and store the result
vector<int> result = solution.twoSum(nums, target);
// Output the result if a valid pair is found
if (!result.empty()) {
cout << result[0] << " " << result[1] << endl;
}
return 0;
}Java
import java.util.Scanner;
class Solution {
// Function to find two indices such that their sum equals the target
public int[] twoSum(int[] nums, int target) {
// Outer loop to pick the first number
for (int i = 0; i < nums.length; i++) {
// Inner loop to iterate through the remaining numbers
for (int j = i + 1; j < nums.length; j++) {
// Check if the sum of two numbers matches the target
if (nums[i] + nums[j] == target) {
// Return the indices
return new int[] { i, j };
}
}
}
// Return empty array if no solution is found
return new int[0];
}
}
public class Main { // Changed class name from TwoSum to Main
public static void main(String[] args) {
// Create a scanner object to read input
Scanner sc = new Scanner(System.in);
// Input the size of the array
int n = sc.nextInt();
// Create an array to store the elements
int[] nums = new int[n];
// Input the array elements
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
// Input the target
int target = sc.nextInt();
// Create an instance of the Solution class
Solution solution = new Solution();
// Call the function and get the result
int[] result = solution.twoSum(nums, target);
// Output the result
if (result.length > 0) {
// Output the indices
System.out.println(result[0] + " " + result[1]);
}
// Close the scanner
sc.close();
}
}Python
class Solution:
def twoSum(self, nums, target):
# Outer loop to pick the first number
for i in range(len(nums)):
# Inner loop to iterate through the remaining numbers
for j in range(i + 1, len(nums)):
# Check if the sum of two numbers matches the target
if nums[i] + nums[j] == target:
# Return the indices
return [i, j]
return []
# Input the size of the array
n = int(input())
# Input the array elements
nums = list(map(int, input().split()))
# Input the target
target = int(input())
# Create an instance of the Solution class
solution = Solution()
# Get result and print
result = solution.twoSum(nums, target)
if result:
# Output the indices
print(result[0], result[1]) Javascript
class Solution {
// Function to find two indices such that their sum equals the target
twoSum(nums, target) {
// Outer loop to pick the first number
for (let i = 0; i < nums.length; i++) {
// Inner loop to iterate through the remaining numbers
for (let j = i + 1; j < nums.length; j++) {
// Check if the sum of two numbers matches the target
if (nums[i] + nums[j] === target) {
// Return the indices
return [i, j];
}
}
}
// Return empty array if no solution is found
return [];
}
}
// Input
// Input the size of the array
const n = parseInt(prompt());
// Input the array elements
const nums = prompt().split(' ').map(Number);
// Input the target
const target = parseInt(prompt());
// Create an instance of the Solution class
const solution = new Solution();
// Call the function and store the result
const result = solution.twoSum(nums, target);
// Output the result if a valid pair is found
if (result.length > 0) {
// Output the indices
console.log(result[0], result[1]);
}
Time Complexity : O(n²)
- The outer loop runs through each element in the array, so it iterates n times, where n is the length of the array.
- For each iteration of the outer loop, the inner loop checks every subsequent element in the array. In the worst case, for each outer loop iteration, the inner loop will iterate n - 1 times.
Thus, the total number of comparisons is roughly n * (n - 1) / 2, which simplifies to O(n²).
Space Complexity : O(1)
Auxiliary Space Complexity: O(1)
The auxiliary space complexity is O(1) since the algorithm uses a constant amount of extra space, without creating additional data structures that grow with the input size.
Total Space Complexity: O(1)
The total space complexity is O(n) since we are taking input array of length n
Instead of checking all pairs with a brute force approach, we can optimize by tracking numbers we've seen. This allows us to find the required pair in a single pass .
Optimal Approach
Intuition
When we approach the problem using brute force, we end up checking every possible pair of numbers, which leads to many redundant comparisons. This becomes inefficient as we repeatedly check pairs we've already considered. Instead of continuing with this method, we can optimize by skipping unnecessary checks.
To do this, we can use a hashmap to keep track of the numbers we've already seen as we iterate through the array. The key idea is to check if the complement of the current number (the number that, when added to the current number, equals the target) exists in the hashmap.
The complement is simply the difference between the target sum and the current number. For example, if the target is 9 and the current number is 7, the complement would be 9 - 7 = 2. So, we are essentially asking, "Have I already seen the number that will add with this one to make the target sum?"
If the complement exists in the hashmap, it means the current number and a previously seen number together form a valid pair that adds up to the target
The reason we check for the complement is simple: for every number, we want to see if we’ve already encountered the number that would complete the pair. If we’ve seen it before, we’ve found the solution and can stop further checks.
If we don’t find the complement in the hashmap, we simply add the current number to the hashmap and continue. This way, the hashmap is storing all numbers we've passed through, which helps us efficiently check future numbers for matching pairs. This approach drastically reduces the number of comparisons, allowing us to find the valid pair much faster.
What is a Hashmap ?
A hashmap (also known as a hash table) is a data structure that stores data in key-value pairs. Each key is unique, and values are accessed using the key. The hashmap uses a hash function to map the keys to indices in an underlying array, which allows for very fast retrieval, insertion, and deletion operations—typically in constant time, O(1). This makes hashmaps extremely efficient for tasks where you need to quickly look up values based on a key.
Approach
Step 1: Initialize the Hash Map
Start by creating an empty hash map (unordered_map). This will store each number in the array as a key and its corresponding index as the value. The purpose of this hash map is to quickly check if the complement of the current number (target - current number) has been seen before.
Step 2: Iterate Through the Array
Loop through the array, one number at a time. For each number, we will calculate its complement (target - current number) and check if it exists in the hash map.
Step 3: Check If Complement Exists in Hashmap
Inside the loop, check if the complement of the current number exists in the hash map. If the complement is found, it means we have already seen a number earlier that, when added to the current number, equals the target. In this case, we return the indices of both numbers.
Step 4: Store the Current Number in the Hashmap
If the complement doesn’t exist in the hash map, store the current number and its index in the hash map. This allows us to use this number for future complements as we continue iterating through the array.
Let us understand this with a video,
Two Sum-Optimal-Approach
Dry run
First Iteration (i = 0):
- Current number: nums[0] = 11
- Calculate complement: complement = target - nums[0] = 9 - 11 = -2
- Check if -2 exists in the hash map: No
- Add current number and its index to the hash map: mp = {11: 0}
Second Iteration (i = 1):
- Current number: nums[1] = 7
- Calculate complement: complement = target - nums[1] = 9 - 7 = 2
- Check if 2 exists in the hash map: No
- Add current number and its index to the hash map: mp = {11: 0, 7: 1}
Third Iteration (i = 2):
- Current number: nums[2] = 15
- Calculate complement: complement = target - nums[2] = 9 - 15 = -6
- Check if -6 exists in the hash map: No
- Add current number and its index to the hash map: mp = {11: 0, 7: 1, 15: 2}
Fourth Iteration (i = 3):
- Current number: nums[3] = 2
- Calculate complement: complement = target - nums[3] = 9 - 2 = 7
- Check if 7 exists in the hash map: Yes, 7 is found at index 1
- We have found the pair (7, 2) which adds up to 9
- Return the indices: [1, 3]
Output:[1, 3]
Code for All Languages
C++
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
class Solution {
public:
// Function to find the indices of two numbers that add up to the target
vector<int> twoSum(vector<int>& nums, int target) {
// Map to store numbers and their indices
unordered_map<int, int> mp;
// Iterate through the array to find the pair
for (int i = 0; i < nums.size(); i++) {
// Calculate the complement
int complement = target - nums[i];
// If the complement exists in the map, return the indices
if (mp.count(complement)) {
return {mp[complement], i};
}
// Store the current number and its index in the map
mp[nums[i]] = i;
}
// Return {-1, -1} if no solution is found (shouldn't happen per problem statement)
return {-1, -1};
}
};
int main() {
// Input for the number of elements in the array
int n, target;
cin >> n;
// Create a vector to store the array elements
vector<int> nums(n);
// Input for the array elements
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
// Input for the target value
cin >> target;
// Create an instance of Solution class
Solution solution;
// Find and output the indices of the two numbers
vector<int> result = solution.twoSum(nums, target);
// Print the indices
cout << result[0] << " " << result[1] << endl;
return 0;
}Java
import java.util.HashMap;
import java.util.Scanner;
class Solution {
// Function to find the indices of two numbers that add up to the target
public int[] twoSum(int[] nums, int target) {
// Map to store numbers and their indices
HashMap<Integer, Integer> map = new HashMap<>();
// Iterate through the array to find the pair
for (int i = 0; i < nums.length; i++) {
// Calculate the complement
int complement = target - nums[i];
// If the complement exists in the map, return the indices
if (map.containsKey(complement)) {
return new int[]{map.get(complement), i};
}
// Store the current number and its index in the map
map.put(nums[i], i);
}
// Return {-1, -1} if no solution is found (shouldn't happen per problem statement)
return new int[]{-1, -1};
}
}
public class TwoSum {
public static void main(String[] args) {
// Create a scanner object for input
Scanner sc = new Scanner(System.in);
// Input for the number of elements in the array
int n = sc.nextInt();
// Create an array to store the numbers
int[] nums = new int[n];
// Input for the array elements
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
// Input for the target value
int target = sc.nextInt();
// Create an instance of Solution class
Solution solution = new Solution();
// Find and output the indices of the two numbers
int[] result = solution.twoSum(nums, target);
// Print the indices
System.out.println(result[0] + " " + result[1]);
// Close scanner
sc.close();
}
}
Python
def two_sum(nums, target):
# Dictionary to store numbers and their indices
num_map = {}
# Iterate through the list to find the pair
for i, num in enumerate(nums):
# Calculate the complement
complement = target - num
# If the complement exists in the map, return the indices
if complement in num_map:
return [num_map[complement], i]
# Store the current number and its index in the map
num_map[num] = i
# Return [-1, -1] if no solution is found (shouldn't happen per problem statement)
return [-1, -1]
if __name__ == "__main__":
# Input number of elements
n = int(input().strip())
# Input array elements
nums = list(map(int, input().split()))
# Input target value
target = int(input().strip())
# Get the result and print indices
result = two_sum(nums, target)
print(result[0], result[1])
Javascript
// Function to find the indices of two numbers that add up to the target
function twoSum(nums, target) {
// Map to store numbers and their indices
let map = new Map();
// Iterate through the array to find the pair
for (let i = 0; i < nums.length; i++) {
// Calculate the complement
let complement = target - nums[i];
// If the complement exists in the map, return the indices
if (map.has(complement)) {
return [map.get(complement), i];
}
// Store the current number and its index in the map
map.set(nums[i], i);
}
// Return [-1, -1] if no solution is found (shouldn't happen per problem statement)
return [-1, -1];
}
// Input section
let n = parseInt(prompt("Enter the number of elements:")); // Input for the number of elements in the array
let nums = [];
// Input for the array elements
for (let i = 0; i < n; i++) {
nums.push(parseInt(prompt(`Enter element ${i + 1}:`)));
}
// Input for the target value
let target = parseInt(prompt("Enter the target value:"));
// Find and output the indices of the two numbers
let result = twoSum(nums, target);
// Print the indices
console.log(result[0] + " " + result[1]);
Time Complexity : O(n)
We are iterating through the array once, where n is the length of the array. For each element, we perform constant time operations (checking if the complement exists in the hashmap and adding an element to the map). Therefore, the overall time complexity is linear, O(n).
Space Complexity: O(n)
Auxiliary Space Complexity: O(n)
The auxiliary space complexity is O(n) since the hash map is an additional data structure used by the algorithm, and its size grows linearly with the input size n.
Total Space Complexity: O(n)
The total space complexity is O(n) because we are storing both the elements and their indices in a hash map, which requires space proportional to the number of elements in the array.
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Given an array nums of nn integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:
0 ≤ a,b,c,d < n
a,b,c and d are distinct indices
nums[a] + nums[b] + nums[c] + nums[d] = target