src.three_sum

Classes

Solution()

class src.three_sum.Solution[source][source]
threeSum(nums: list[int]) → list[list[int]][source]

Thought process

  • Broad idea: We sort our array, then take a value a and consider the values to the l and r. Since the array is sorted moving r closer to l will decrease the sum and moving l closer to r will increase the sum.

  • We can skip positive integers, since it is impossible to sum to 0 (e.g. [1, 2, 3])

  • We can skip duplicates to avoid duplicates in our result

  • Basic two pointer setup so 1. init pointers 2. loop while they havent crossed over

  • Check the 3 cases of the sum being too large, too small, or just right

  • If the sum is just right then append the result, move the pointers and skip duplicates

Notes

  • time complexity: \(O(n\log n + n^2)\) -> \(O(n^2)\)

  • space complexity: \(O(1)\) / \(O(n)\) depending on the implementation of sort