In this article, we will learn to analyze and resolve the 2Sum problem by using two pointers algorithm and hash table data structure
Two pointers algorithm uses two indices and walks inward from both ends to reduce the iteration time when searching elements in a sorted linear collection
Hash table has a better performance than other collections in terms of looking up elements
The 2Sum problem
Given an array of integers
a[n]
and an integer numberk
as a target sumDetermine whether there is a pair of elements
a[i]
anda[j]
that sums exactly tok
Example
Given an array a [1, 3, 7] and k = 8 then the answer is
true
, but given k=5 then the answer isfalse
Given an array a [4, -9, 0, 11, 6, -20, 1, 7] and k = -14 then the answer is
true
, but given k = -15 then the answer isfalse
Approach 1: Brute force
- Use 2 for-loop to try all pairs in the given array
a
to see if any of them add up tok
import java.util.Arrays;
public class TwoSum_BruteForce {
static boolean bruteForce(int[] a, int k) {
for (int i = 0; i < a.length ; i++) {
for (int j = i+1; j < a.length; j++) {
if (a[i] + a[j] == k) return true;
}
}
return false;
}
public static void main(String[] args) {
int[] a = {1, 3, 7};
System.out.println(bruteForce(a, 8));
System.out.println(bruteForce(a, 5));
int[] b = {4, -9, 0, 11, 6, -20, 1, 7};
System.out.println(bruteForce(b, -14));
System.out.println(bruteForce(b, -15));
}
}
- Output
true
false
true
false
Time complexity: O(n2) as with each element, the algorithm loops through the array which takes O(n) time
Space complexity: O(1)
Approach 2: Two pointers
Sort the given array
Walk two indices
i
andj
inward from both ends of the array. Whilei
still less thanj
, calculate the sums
of their corresponding elements. Ifs
equals to the givenk
then returntrue
and exit the algortihm immediately. Ifs
is less thank
, increasesi
by 1, otherwise decreasesj
by 1Finally, return
false
as no pairs has sum equals tok
import java.util.Arrays;
public class TwoSum_TwoPointers {
static boolean twoPointers(int[] a, int k) {
Arrays.sort(a);
int i = 0;
int j = a.length - 1;
while (i < j) {
int sum = a[i] + a[j];
if (sum == k) {
return true;
} else if (sum < k) {
i++;
} else {
j--;
}
}
return false;
}
public static void main(String[] args) {
int[] a = {1, 3, 7};
System.out.println(twoPointers(a, 8));
System.out.println(twoPointers(a, 5));
int[] b = {4, -9, 0, 11, 6, -20, 1, 7};
System.out.println(twoPointers(b, -14));
System.out.println(twoPointers(b, -15));
}
}
- Output
true
false
true
false
Time complexity: O(nlogn) due to the cost of sorting
Space complexity: O(1)
Approach 3: Hash table
Create a new HashSet
h
Loop through the given array
a
. For each array elementa[i]
, check if existing an elementa[j]
thata[j] = k - a[i]
. If yes returntrue
and exit the algorithm immediately, otherwise adda[i]
intoh
Finally, return
false
as no pairs has sum equals tok
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
public class TwoSum_HashTable {
static boolean hashTable(int[] a, int k) {
HashSet<Integer> h = new HashSet<>();
for (int i = 0; i < a.length ; i++) {
if (h.contains(k - a[i])) return true;
h.add(a[i]);
}
return false;
}
public static void main(String[] args) {
int[] a = {1, 3, 7};
System.out.println(hashTable(a, 8));
System.out.println(hashTable(a, 5));
int[] b = {4, -9, 0, 11, 6, -20, 1, 7};
System.out.println(hashTable(b, -14));
System.out.println(hashTable(b, -15));
}
}
- Output
true
false
true
false
Time complexity: O(n) as with each element, the algorithm looks up in the hash table which takes O(1) time
Space complexity: O(n) as the algorithm use a hash table size
n