LeetCode 15. 3Sum — Python Solution

Blind 75 — Programming & Technical Interview Questions — Explanation Series

The problem:

I recommend reading 167. Two Sum II before this problem.

The explanation:

The problem is a great addition to the sum problems, and pretty different to Two Sum but builds of Two Sum II. The basic solution would be O(n³) and use three for-loops to check every single combination, this of course would take an extremely long time and not the most efficient solution. Using this same intuition this can be compressed into an O(n²) solution. The first step in this solution is sorting the array, this allows us to use a very similar solution to Two Sum II. What you can do is loop through the entire array, holding that element constant, then use left and right pointers to converge on a 0-sum.

The Sort Solution— O(n²):

First we store the length of the array and then initialize the results array. Now if the array doesn’t even have three element, return an empty array. Now we sort the array, then enumerate through the array (could’ve just used nums[i], but enumerate is cleaner). Inside this loop if the value is the same as the previous value we already have determined a solution for this number so we…