Two Sum Problem with Two Pointers and Hash Table

One would resolve the two sum problem by using two pointers or a hash table algorithm

If the input array is sorted or the output does not require returning array indices, one would use both two-pointers and hash table algorithm
If the input array is not sorted and the output requires returning array indices, one would use the hash table algorithm

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

Two Sum problem 1

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: 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(n²) as with each element, the algorithm loops through the array which takes O(n) time
Space complexity: O(1)

Approach: Two pointers

Sort the given array
Walk two indices i and j inward from both ends of the array. While i is 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 algorithm immediately. If s is less than k, increases i by 1, otherwise decreases j by 1
Finally, return false as no pair has a sum equal 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: 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 pair has a sum equal 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

Two Sum problem 2

Given an array of integers nums and an integer number k as a target sum. Return indices of the two numbers such that they add up to k

Example

Input: nums = [1, 3, 7], k = 8. Output: [0, 2]
Input: nums = [4, -9, 0, 11, 6, -20, 1, 7], k = -14. Output: [4, 5]

Approach: HashTable

Loops through the array nums and puts each element value nums[i] and index i into a HashMap as key and value

Each time, check if the map contains key k - nums[i] then return {map.get(k - nums[i]), i} as the result

public int[] twoSum(int[] nums, int k) {  
    Map<Integer, Integer> map = new HashMap<>();
    for (int i=0; i<nums.length; i++) {
        if (map.containsKey(k - nums[i])) {
            return new int[]{map.get(k - nums[i]), i};
        }
        map.put(nums[i], i);
    }

    return null;
}

Time complexity: O(n)
Space complexity: O(n)

Algorithm