Algorithm

Three Number Sum

  Problem Given an array of distinct integers sums and an integer representing the target sum. Find all triple numbers in the...

Written by Vortana Say · 46 sec read

 

Problem

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

Find all triple numbers in the array sums that adds up to the target sum.

We cannot add a number to itself to get the target sum.

Example 1:

Input: nums = [-8, -6, 1, 2, 3, 6, 7, 15], target = 1

Output: [[-8, -6, 15], [-8, 2, 7], [-8, 3, 6], [-6, 1, 6]]

Explanation:
-8 – 6 + 15 = 1
-8 + 2 + 7 = 1
-8 + 3 + 6 = 1
-6 + 1 + 6 = 1

Solution: Sort and two pointers

We sort the input array in ascending order and use two pointers to find out two other numbers that sum with current number to be target number.

Example

Input: nums = [15, -6, 2, 1, 6, 7, 3, -8], target = 1

Output: [[-8, -6, 15], [-8, 2, 7], [-8, 3, 6], [-6, 1, 6]]

Explanation

sorted num = [-8, -6, 1, 2, 3, 6, 7, 15]

currentNumber = -8
LP = -6
RP = 15
-8 – 6 + 15 = 1
-8 + 1 + 7 = 0
-8 + 2 + 7 = 1
-8 + 3 + 6 = 1

currentNumber = -6
LP = 1
RP = 15
-6 + 1 + 15 = 10
-6 + 1 + 7 = 2
-6 + 1 + 6 = 1
-6 + 2 + 3 = -1

currentNumber = 1
LP = 2
RP = 15
1 + 2 + 15 = 18
1 + 2 + 7 = 10
1 + 2 + 6 = 9
1 + 2 + 3 = 6

currentNumber = 2
LP = 3
RP = 15
2 + 3 + 15 = 20
2 + 3 + 7 = 12
2 + 3 + 6 = 11

currentNumber = 3
LP = 7
RP = 15
3 + 6 + 15 = 24
3 + 6 + 7 = 16

currentNumber = 6
LP = 6
RP = 15
3 + 6 + 15 = 24

Complexity Analysis:

  • Time Complexity: O(n^2), where N is the length of the input array. It is double loop because:

    • We traverse through array for each number – O(n)
    • In each number, we have LP and RP that traverse through the rest of the element in the array – O(n)
  • Space Complexity: O(n) – we create array list to store triplet (array of three numbers)

Kotlin