15. 3Sum
https://leetcode.com/problems/3sum/
The problem requires us to find all the set of 3 numbers such that they all add up to 0
Approach 1: Nested Loops
The most naive solution is to try every combination of 3 numbers to see if they add up to zero, and store them in res
if they do, else continue looping. In the end, res
will have all the numbers that add up to 0 i.e. our answer
Since we are using three nested loops to iterate over all the combinations, we are going to have a time complexity of n*n*n which will blow up for large arrays, and that is what the leetcode submission results in too (TimeLimitExceeded: passes 311/313 test cases, and fails on the large testcases)
Time Complexity: O(n^3) where n is the length of the array
Space Complexity: O(1)
Approach 2: Target method
The strategy is to basically iterate over the entire array, and basically treat each number as a target for the other numbers to add and cancel out.
We can use linear search to find the target pair of numbers, and to simplify this search we can sort the array first.
To avoid duplicate targets, we will only treat the first copy of every number as a target and if a number equals the one at the previous index, then we can simply continue iterating over the array till we get a new target.
We can keep track of 2 indices, l
and r
if the total = nums[i] + nums[l] + nums[r]
is greater than 0 we know we have to reduce our total so reduce the upper bound nums[r]
by decrementing r
, and if our total is less than 0 we increment the lower bound l
Time Complexity: O(nlogn + n^2) where n is the length of the array
Space Complexity: O(1) [no extra space except res used]
Last updated