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