Problem
You are given an array of n integers and a target sum T. The goal is to determine whether or not there are two numbers x, y in A with x+y=T.
OR
Given an array of integers, find two numbers such that they add up to a specific target number.
Variant: Return the indices instead of the elements in array.
Example
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Solution
There are three approaches to solve this problem - 1) brute force, 2) sort the array and use binary and search, and 3) Using the hashtable. Please scroll down, if you are only interested in the best approach i.e. approach 3 using hashtables.
Video explanation
Here is the video explaining below methods in detail. Please check it out:
Method 1 : Brute Force Method
The first approach is to use brute force which gives time complexity of O(n^2) and space complexity of O(n). We basically just have to loop through the array and for each number we add it to each of other numbers and see if they sum up to 5. If so, we print out the pair. Here is the code for brute force approach:
Code
Java
class Solution {
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
return new int[]{i, j}; // Return indices
}
}
}
return new int[]{-1, -1}; // Return invalid pair if no solution
}
}
Python
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
return [-1, -1] # Return invalid pair if no solution
Complexity
- ⏰ Time complexity:
O(n^2) - 🧺 Space complexity:
O(1)
Method 2 - Use Sorting and Binary Search
A better way would be to sort the array. This takes O(n log n) Then for each x in array A, use binary search to look for T-x. This will take O(nlogn). So, overall search is O(n log n)
Complexity
- ⏰ Time complexity:
O(n log n)for sorting andO (n log n)⇨O(nlogn) - 🧺 Space complexity:
O(1)
Pseudocode
Hers is how the pseudo code will look:
arr = {}; //some array
sortedArr = sort(arr);
for (i = 0; i < arr.length - 1; i++) {
x = arr[i];
bool found = binarySearch(sortedArr, T - x); //Search for T-x in sorted Arrary
if (found)
print "pair", x, T - x;
}
Problem with above approach is, what if x = T/2, then we will find the element, even though it will find the same element again.
Code
Java
class Solution {
public int[] twoSum(int[] nums, int target) {
int[][] indexedNums = new int[nums.length][2];
for (int i = 0; i < nums.length; i++) {
indexedNums[i][0] = nums[i]; // Store value
indexedNums[i][1] = i; // Store index
}
Arrays.sort(indexedNums, (a, b) -> Integer.compare(a[0], b[0])); // Sort by value
for (int i = 0; i < nums.length; i++) {
int complement = target - indexedNums[i][0];
int idx = binarySearch(indexedNums, i + 1, nums.length - 1, complement);
if (idx != -1) {
return new int[]{indexedNums[i][1], indexedNums[idx][1]};
}
}
return new int[]{-1, -1}; // No solution
}
private int binarySearch(int[][] nums, int left, int right, int target) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid][0] == target) return mid;
if (nums[mid][0] < target) left = mid + 1;
else right = mid - 1;
}
return -1; // Not found
}
}
Python
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
indexed_nums = [(val, idx) for idx, val in enumerate(nums)] # Pair values with indices
indexed_nums.sort() # Sort by value
def binary_search(nums: List[tuple], left: int, target: int) -> int:
right = len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid][0] == target:
return mid
elif nums[mid][0] < target:
left = mid + 1
else:
right = mid - 1
return -1
for i, (val, idx) in enumerate(indexed_nums):
complement = target - val
idx_in_sorted = binary_search(indexed_nums, i + 1, complement)
if idx_in_sorted != -1:
return [idx, indexed_nums[idx_in_sorted][1]]
return [-1, -1] # No solution
Method 3 - Using Sorting and 2 Pointer Approach
Assuming array sorted in ascending order. Now we take first and last element, and sum them up. If sum is equal to T, we have found the pair, but if sum is greater than T, we reduce right pointer by 1, or increment left pointer otherwise.
Code
Java
If we had to just return the numbers:
private static int[] twoSum(int[] nums, int target) {
Arrays.sort(nums);
int left = 0;
int right = nums.length - 1;
while(left < right) {
if(nums[left] + nums[right] == target) {
return new int[] {nums[left], nums[right]};
} else if (nums[left] + nums[right] < target) {
left++;
} else {
right--;
}
}
return new int[] {};
}
Returning indices
class Solution {
public int[] twoSum(int[] nums, int target) {
int[][] indexedNums = new int[nums.length][2];
for (int i = 0; i < nums.length; i++) {
indexedNums[i][0] = nums[i];
indexedNums[i][1] = i;
}
Arrays.sort(indexedNums, (a, b) -> Integer.compare(a[0], b[0]));
int l = 0, r = nums.length - 1;
while (l < r) {
int sum = indexedNums[l][0] + indexedNums[r][0];
if (sum == target) {
return new int[]{indexedNums[l][1], indexedNums[r][1]};
} else if (sum < target) {
l++;
} else {
r--;
}
}
return new int[]{-1, -1};
}
}
Python
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
indexed_nums = [(val, idx) for idx, val in enumerate(nums)]
indexed_nums.sort() # Sort based on values
l, r = 0, len(indexed_nums) - 1
while l < r:
sum_lr = indexed_nums[l][0] + indexed_nums[r][0]
if sum_lr == target:
return [indexed_nums[l][1], indexed_nums[r][1]]
elif sum_lr < target:
l += 1
else:
r -= 1
return [-1, -1] # No solution
Complexity
- ⏰ Time complexity:
O(n log n)(From sorting it takes O(nlogn) time and for 2 pointer technique takes O(n) time) - 🧺 Space complexity:
O(1)
Method 4 - Use Hash Table 🏆
I have already mentioned in problem in the application of hash table here. The best way would be to insert every element into a hash table (without sorting). This takes O(n) as constant time insertion. Then for every x, we can just look up its complement, T-x, which is O(1). Overall it takes will be O(n).
Pseudocode
Here is how the pseudocode will look.
Let arr be the given array.
And T be the given sum
hash = {}
for (i = 0 i < arr.length - 1; i++) {
// key is the element and value is its index.
num = arr[i]
complement = T - num
if complement in hash and hash[complement] < i:
print("Pair:", i, ",", hash[complement], "has sum", T)
hash[num] = i
}
Code
Java
Here is the code which returns the index of the 2 numbers which add up to T:
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int compliment = target - nums[i];
if (map.containsKey(compliment)) {
return new int[]{map.get(compliment), i};
}
map.put(nums[i], i);
}
return new int[]{-1, -1}; // No solution
}
}
Python
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
index_map: dict[int, int] = {}
for i, num in enumerate(nums):
complement = target - num
if complement in index_map:
return [index_map[complement], i]
index_map[num] = i
return [-1, -1] # No solution
Dry Run
For example, if we hash the example array we’ll have this hash table:
Key Value
5 5 - 5 = 0
3 5 - 3 = 2
7 5 - 7 = -2
0 5 - 0 = 5
1 5 - 1 = 4
4 5 - 4 = 1
2 5 - 3 = 2
Please let us know if you know any other approach. Thanks.