Coding Problem: Two Number Sum

In this blog post, we will write a program for Two Number Sum coding problem.

Problem Statement:

Write a method/function that takes in a non-empty array of distinct integers and an integer representing a target sum. If any two numbers in the input array sum up to the target sum, the method should return them in an array, in any order. If no two numbers sum up to the target sum, the method should return an empty array.

Note that the target sum has to be obtained by summing two different integers in the array; you can't add a single integer to itself in order to obtain the target sum.

You can assume that there will be at most one pair of numbers summing up to the target sum.

Sample Input:

array = [3, 5, -4, 8, 11, 1, -1, 6], targetSum = 10

Sample Output:

[11, -1] // the numbers could be in reverse order

Solution:

Method 1: Naive approach: Use two for loops

We can use two for loops to sum all possible pairs of numbers in the input array.

Time Complexity: O(n²), where n is length of an array.
Space Complexity: O(1)

Using Java:

import java.util.*;

public class TwoNumberSum {
    /**
     * Two number sum:
     * Naive approach:
     * Use two nested for loops and check if the sum of any two elements
     * in the array is equal to the given target
     *
     * Time Complexity: O(n^2), where n is length of an array.
     * Space Complexity: O(1)
     *
     * @param array non-empty array of distinct integers
     * @param targetSum targetSum integer representing a target sum
     * @return array of two numbers representing target sum
     */
    public static int[] twoNumberSum(int[] array, int targetSum) {
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = i + 1; j < array.length; j++) {
                if ((array[i] + array[j]) == targetSum) {
                    return new int[]{array[i], array[j]};
                }
            }
        }
        return new int[0];
    }
}

Using Python:

def two_number_sum(array, target_sum):
    for i in range(len(array) - 1):
        for j in range(i + 1, len(array)):
            if array[i] + array[j] == target_sum:
                return [array[i], array[j]]
    return []

Method 2: Using hash table (Most Efficient)

1. Realize that for every number x in the input array, you are essentially trying to find a corresponding number y such that x + y = targetSum.
2. We need to store every number in a hash table, solving the equation mentioned in point 1. for every number, and checking if the y that you find is stored in the hash table.

Steps:

• Initialize a hash table.
• Iterate over the elements of the array
• For every element in the array:
  • Check if its complement (targetSum - element) exists in the table or not. If the complement exists return the complement and number.
  • If the complement does not exists, put the element in the table and move to the next iteration.

Using Java:

import java.util.*;

public class TwoNumberSum {
    
    /**
     * Two number sum:
     * Realize that for every number x in the input array, you are essentially
     * trying to find a corresponding number y such that x + y = targetSum.
     *
     * Time Complexity: O(n), where n is length of an array.
     * Space Complexity: O(n), where n is length of an array.
     *
     * @param array non-empty array of distinct integers
     * @param targetSum integer representing a target sum
     * @return array of two numbers representing target sum
     */
    public int[] twoNumSum(int[] array, int targetSum) {
        Set nums = new HashSet<>();

        for (int num: array) {
            int complement = targetSum - num;

            if (nums.contains(complement)) {
                return new int[]{complement, num};
            } else {
                nums.add(num);
            }
        }
        return new int[0];
    }
}

Using Python:

def two_num_sum(array, target_sum):
    nums = {}
    for num in array:
        complement = target_sum - num

        if complement in nums:
            return [complement, num]
        else:
            nums[num] = True
    return []