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 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

  • Use 2 for-loop to try all pairs in the given array a to see if any of them add up to k
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 and j inward from both ends of the array. While i still less than j, calculate the sum s of their corresponding elements. If s equals to the given k then return true and exit the algortihm immediately. If s is less than k, increases i by 1, otherwise decreases j by 1

  • Finally, return false as no pairs has sum equals to k

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 element a[i], check if existing an element a[j] that a[j] = k - a[i]. If yes return true and exit the algorithm immediately, otherwise add a[i] into h

  • Finally, return false as no pairs has sum equals to k

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

Algorithm