Two Number Sum

Problem

Given an array of distinct integers sums and an integer representing the target sum.

Find if there’s a pair of numbers in the array sums that adds up to the target sum.

If such pair exists, return the pair in any order; otherwise return an empty array. We cannot add a number to itself to get the target sum.

Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [2,7]
Explanation: Because nums[0] + nums[1] == 9, we return [2, 7].

Example 2:
Input: nums = [3,2,4], target = 6
Output: [2,4]

Example 2:
Input: nums = [3,3], target = 7
Output: []

Approach 1: Brute force

For each number, iterate through the rest of the array; if adding any number in the rest of the array to the number yields the target sum, return the pair.

Example

Input: nums = [1,3,2,7,11,15], target = 9

Adding 1 to [3,2,7,11,15] to check if it equal 9; no pair found

Adding 3 to [2,7,11,15] to check if it equal 9; no pair found

Adding 2 to [7,11,15] to check if it equal 9; pair(2, 7) found

Complexity Analysis:

• Time Complexity: O(N^2), where N is the length of the input array.

• Space Complexity: O(1)

Kotlin

Approach 2: One-pass Hash table

n: target number

x: current number

y: number needed to sum up to the target value

Formula: x + y = n => y = n – x

• Traverse through the array nums
• During traversing each number, we check if y is stored in hash table.
  • If no, we store x and its index in the hash table
  • If yes, we return pair (x, y)

Access to hash table is constant time

Example

Input: nums = [1,3,2,7,11,15], target = 9

current number = 1; y = 9 – 1 = 8

Is 8 in hash table? no => we store number 1 in hash table

{ [1: 0] }

current number = 3; y = 9 – 3 = 6

Is 6 in hash table? no => we store number 3 in hash table

{ [1: 0], [3:1] }

current number = 2; y = 9 – 2 = 7

Is 7 in hash table? no => we store number 2 in hash table

{ [1: 0], [3:1], [2: 2] }

current number = 7; y = 9 – 7 = 2

Is 2 in hash table? yes => then we return pair [2, 7]

Complexity Analysis:

• Time Complexity: O(N), where N is the length of the input array.

• Space Complexity: O(N)

Kotlin

Approach 3: Sort and two pointers

We sort the input array in ascending order and use two pointers to find the pair in the array.

Example

Input: nums = [1,7,3,2,-15,11], target = 9

Sorted nums = [-15,1,2,3,7,11]

LP = -15; RP = 11

LP + RP = -15 + 11 = -4 < 9

LP = 1; RP = 11

LP + RP = 1 + 11 = 12 > 9

LP = 1; RP = 7

LP + RP = 1 + 7 = 8 < 9

LP = 2; RP = 7

LP + RP = 2 + 7 = 9 = 9

Return pair (2, 7)

Complexity Analysis:

• Time Complexity: O(N · log(N)), where N is the length of the input array.

• Space Complexity: O(1)

Kotlin