Exploring different approaches to the popular data structure and algorithm problem, two-sum. Simply explained!
The Two-Sum problem is a classic data structure and algorithm (DSA) problem that is frequently asked during coding interviews. The problem statement is simple: Given an array of integers array and an integer targetSum, find two numbers in the array such that they add up to the target. You may assume that each input would have exactly one solution, and you may not use the same element twice.
In this post, we will explore various ways to solve the Two-Sum problem, discussing their time and space complexities, as well as the pros and cons of each approach. I would assume that you understand basic data structure i.e. Array, Map, Set, etc
- Brute Force Approach
The most straightforward approach to solving the Two-Sum problem is to use a nested loop to check all possible pairs of numbers in the array. For each pair, we check if their sum is equal to the target value. Below is an example solution:
// Java
public static int[] twoSum(int[] array, int targetSum) {
for(int i = 0; i < array.length; i++) {
for(int j = 0; j < array.length; j++) {
if(j == i) continue;
int sum = array[i] + array[j];
if(sum == targetSum) {
return new int[] { array[i], array[j] } ; }
}
}
return new int[0];
}
// Swift
func twoSum(_ array: inout [Int], _ targetSum: Int) -> [Int] {
for (key, value) in array.enumerated() {
for (subKey, subValue) in array.enumerated() {
if(key == subKey) { continue }
let sum = value + subValue
if(sum == targetSum) { return [value, subValue] }
}
}
return []
}
// Javascript
function twoSum(array, targetSum) {
for(let i = 0; i < array.length; i++) {
for(let j = 0; j < array.length; j++) {
if(i === j) continue;
if(array[i] + array[j] === targetSum) {
return [ array[i], array[j] ]; }
}
}
return [];
}
// C#
public static int[] TwoSum(int[] array, int targetSum) {
for(int i = 0; i < array.Length; i++) {
for(int j = 0; j < array.Length; j++) {
if(i == j) continue;
if(array[i] + array[j] == targetSum) {
return new int[] { array[i], array[j] };
}
}
}
return new int[0];
}
Time complexity: O(n²), Space complexity: O(1)
This approach is not very efficient, especially for large arrays, as it requires checking all possible pairs of numbers 😬
- HashMap / Dictionary Approach
A more efficient approach to solving the Two-Sum problem is to use a hash-based data structure i.e. map or dictionary to store the numbers in the array and their indices.
// Java
public static int[] twoSum(int[] array, int targetSum) {
Map<Integer, Integer> map = new HashMap<>();
int index = 0;
while(index < array.length) {
int num = targetSum - array[index];
if(map.containsKey(num)) {
return new int[] { num, array[index] }; }
map.put(array[index], num);
index++;
}
return new int[0];
}
// Swift
func twoSum(_ array: inout [Int], _ targetSum: Int) -> [Int] {
var dictionary: [Int: Int] = [:]
for num in array {
let difference = targetSum - num
if let contains = dictionary[difference] {
return [ contains, difference ]
}
dictionary[num] = difference
}
return []
}
//Javascript
function twoSum(array, targetSum) {
const map = new Map();
for(const num of array) {
let difference = targetSum - num;
if(map.has(difference)) {
return [ difference, map.get(difference) ]
}
map.set(num, difference)
}
return [];
}
//C#
public static int[] TwoSum(int[] array, int targetSum) {
Dictionary<int, int> dictionary = new Dictionary<int, int>();
foreach(int num in array) {
int difference = targetSum - num;
if(dictionary.ContainsKey(difference)) {
return new int[] { difference, num };
}
dictionary.Add(num, difference);
}
return new int[]{};
}
Time complexity: O(n), Space complexity: O(n)
This solution is trickier than the first (brute-force) approach, and here is the catch. When we traverse each element of array , we only know the array[index] and the targetSum at every interval. So we can derive the missingby applying the following math formula:
targetSum = missingNumber + currentNumber
missingNumber = targetSum - currentNumber
We will keep associating the missing number with the current number until we’re able to find a duplicate. This approach is faster than the brute force approach, as it only requires a single pass-through, however it requires additional space to store the hash map 😉
- Using Set Approach
This is quite similar to the previous solution, and infact I would regard it as a simplified version of the earlier solution (syntax-wise), the logic still remains the same except for the data-structure that would be used in storing our two numbers, so let’s take a look at this implementation:
// Java
public static int[] twoSum(int[] array, int targetSum) {
Set<Integer> set = new HashSet<Integer>();
int index = 0;
while(index < array.length) {
int num = targetSum - array[index];
if(set.contains(num)) { return new int[] { array[index], num }; }
set.add(array[index]);
index++;
}
return new int[0];
}
// Swift
func twoSum(_ array: inout [Int], _ targetSum: Int) -> [Int] {
var set: Set<Int> = []
var index = 0
while(index < array.count) {
let num = targetSum - array[index]
if(set.contains(num)) { return [ array[index], num ] }
set.insert(array[index])
index += 1
}
return []
}
// Javascript
function twoSum(array, targetSum) {
const set = new Set();
for(const num of array) {
let difference = targetSum - num;
if(set.has(difference)) { return [ num, difference ]; }
set.add(num)
}
return [];
}
// C#
public static int[] TwoSum(int[] array, int targetSum) {
HashSet<int> set = new HashSet<int>();
int index = 0;
while(index < array.Length) {
int difference = targetSum - array[index];
if(set.Contains(difference)) {
return new int[] { array[index], difference };
}
set.Add(array[index]);
index++;
}
return new int[]{};
}
The time and space complexity compare to the previous solution using Map or Dictionary remains the same
- Sorting and Two-pointer Technique
Another approach to solve the Two-Sum problem is to first sort the array and then use two pointers to find the pair of numbers that add up to the targetSum. Let’s take a glance at this solution:
// Java
public static int[] twoSum(int[] array, int targetSum) {
Arrays.sort(array);
int left = 0;
int right = array.length - 1;
while(left < right){
int sum = array[left] + array[right];
if(sum == targetSum) {
return new int[] { array[left], array[right] } ;
} else if (sum < targetSum) {
left++;
} else {
right--;
}
}
return new int[]{};
}
// Swift
func twoSum(_ array: inout [Int], _ targetSum: Int) -> [Int] {
array.sort()
var left = 0
var right = array.count - 1
while(left < right){
let sum = array[right] + array[left]
if(sum == targetSum) {
return [ array[right], array[left] ]
} else if (sum < targetSum) {
left += 1
} else if (sum > targetSum) {
right -= 1
}
}
return []
}
// Javascript
function twoSum(array, targetSum) {
array.sort((a, b) => a - b);
var left = 0;
var right = array.length - 1;
while(left < right) {
var sum = array[left] + array[right];
if(sum === targetSum) {
return [ array[left], array[right] ];
} else if (sum < targetSum) {
left++;
} else {
right--;
}
}
return [];
}
// C#
public static int[] TwoSum(int[] array, int targetSum) {
Array.Sort(array);
int left = 0;
int right = array.Length - 1;
while(left < right) {
int sum = array[left] + array[right];
if(sum == targetSum) {
return new int[]{ array[left], array[right] };
} else if (sum < targetSum) {
left++;
} else {
right--;
}
}
return new int[]{};
}
Time complexity: O(n log n) for sorting, O(n) for finding the pair, Space complexity: O(n) for storing sorted array
We first sort the array in ascending order (which can also be done in descending order), and then we start traversing through the elements of the array from both the left and the right. The thought process is simple: we start with the first and last elements of the array, and if their sum is lesser than the targetSum, it means that the first item is still further to the right of the sorted array, and vice versa. We repeat this process until the sum is equal to the targetSum, and then we break out of the loop.
This approach has a slightly higher time complexity than the hash map approach due to the sorting step. However, it does not require additional space to store a hash map.
Conclusion
The Two-Sum problem can be solved using various approaches, each with its own trade-offs in terms of time and space complexity. Depending on the specific requirements and constraints of a given problem, you can choose the most suitable approach. Remember to practice these solutions and understand their underlying concepts, as they can be helpful during coding interviews and real-world problem-solving.
Please give a clap and share, stay tune for Episode 2 🙏