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

Learn more about Hash table

Follow HelloKoding