15–3SUM
Restating Info We’re Already Given:
- Classic 3SUM: find all triplets of 3 indices that sum to 0
Questions/Clarifications to Possibly Ask Interviewer (If starting information we’re given isn’t sufficient to begin):
- For each outputted triplet, do the indices i, j, and k have to be in ascending/descending order?
- Do the indices themselves have to be in a sorted order?
- What do we return if the list contains less than 3 numbers
Discuss Naive Solution:
We can have a triple for loop that runs for every 3 unique indices and checks if their sum == 0. However, the runtime is O(n³).
Discuss Optimal Solution:
We can reduce this down to O(n²) time by initially sorting the array in increasing order (Python’s default is increasing) and only iterating only over negative values. This ensures that the candidate sum can potentially be 0 because if the first number is positive, there is no way the remaining numbers will sum to 0 (array is now in ascending order, so all numbers afterward will only be higher). We also want to avoid iterating over a negative numbers we’ve tried before, as the first number of the triplet has already been tried. So for all unique negative numbers in nums, we will perform twoSum with a target value equal to the -1 * unique_negative_num as this is the complement of that negative number on the list equal to the remaining elements of the array. For each possible combination, we add it to a triplets list that holds all the triplets summing to 0.
Code Optimal Solution:
Runtime/Space Complexity:
This algorithm runs in O(n²) time. twoSum is O(n²) and we call it at most n times. If we count the outputted triplets array, the space complexity is O(n²) as we could have an array where each triplet sums to 0 (an array of all 0's). If we don’t count the outputted array, the space complexity is O(n) as the dictionary stores a linear amount of indice, target pairs at any given moment.
Test Cases:
- List of all negative numbers, length ≥ 3(should by empty output)
- List of all positive numbers, length ≥ 3 (should by empty output)
- List of length < 3 (should by empty output)
- List of all zeroes, length ≥ 3 (should be all triplets outputted)
- List of positive and negative numbers containing triplet(s) that sum to 0, length ≤ 3 (should return all triplet(s) that sum to 0)
