# HelloKoding

Practical coding guides

# 2Sum Problem

In this article, you will learn to analyze and resolve the 2Sum problem by using two pointers and hash table algorithms

Besides using one pointer to loop through all elements, you can use two pointers to walk inward from both ends of a linear collection, such as array or string, to check a condition

Apart from that, you can also hash collection elements into a hash table to improve the lookup time

## The 2Sum problem

• Given an array of integers `a[n]` and an integer number `k` as a target sum
• Determine whether there is a pair of elements `a[i]` and `a[j]` that sums exactly to `k`

## Example

• Given an array a [1, 3, 7] and k = 8 then the answer is `true`, but given k=5 then the answer is `false`
• 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 is `false`

## Approach 1: Brute force

• Try all pairs in array `a` to see if any of them add up to `k`

TwoSum_BruteForce.java

``````package com.hellokoding.algorithm;

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 array
• Walk two pointers inward from both ends of the array, at each point looking at their sum

TwoSum_TwoPointers.java

``````package com.hellokoding.algorithm;

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

• Add array elements into a hash table
• For each array element `a[i]`, check if existing an element `a[j]` that `a[j] = k - a[i]`

TwoSum_HashTable.java

``````package com.hellokoding.algorithm;

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> hashTable = new HashSet<>();
for (int i = 0; i < a.length ; i++) {
if (hashTable.contains(k - a[i])) return true;
}

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 adds elements into a hash table