Leetcode: Sum Series — Three Sum
The Three sum problem series is an extension of Two Sum problem as constructed in this a previous article. Intuition to solving these problems will heavily borrow on the lessons learnt under patterns and conclusions of the mentioned article.
Three Sum
Problem Statement: Given an array and a value, return a triplet whose sum is equal to the given target otherwise return []
ExampleInput: nums = [12, 3, 4, 1, 6, 9], target = 24
Output: [12, 3, 9]
Explanation: 12 + 3 + 9 = 24
Intuition
- Brute force — loop the array three times to check for possible candidates equal to the target.
- In every iteration — employ two sum solution of finding a number with it’s complement that add to the remainder off the iterated number.
- Sort it — remove the need to have a hashset to record previous seen compliments
Solution 1: Brute force — loop the array three times
def find_triplets(nums: list[int], target: int) -> List[int]:
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
if nums[i] + nums[j] + array[k] == target:
return [nums[i], nums[j], nums[k]]
return []
Review *
- The time complexity —
O(N³)
, space complexity —O(1)
. For each element, it loops the array three times to find a triplet that add upto the target😡.
Solution 2: Employ two sum solution of finding a number with it’s complement that add to the remainder off the iterated number.
def find_triplets(nums: list[int], target: int) -> List[int]:
n = len(nums)
for i in range(n):
seen = set()
rem_target = target - nums[i]
# Two sum problem
for j in range(i + 1, n):
complement = rem_target - nums[j]
if complement in seen:
return [nums[i], nums[j], complement]
else:
seen.add(nums[j])
return []
Review *
- The time complexity —
O(N²)
, space complexity —O(N)
. For each element iteration, it searches for two numbers in the rest of the elements that adds upto theremainder target
🤔(much better!) - However, it uses a hashset to keep a memory of potential complements for later comparisons leading to a space complexity of
O(N)
😵💫.
Solution 2: Sort the input— remove the need to have a hashset
to record previous seen compliments
def find_triplets(nums: list[int], target: int) -> List[int]:
n = len(nums)
array.sort()
for i in range(n):
left, right = i + 1, n - 1
while left < right:
current_sum = nums[i] + nums[left] + nums[right]
if current_sum == target:
return [nums[i], nums[left], nums[right]]
elif current_sum < target:
left += 1
else:
right -= 1
return []
Review *
- The time complexity —
O(N²)
, space complexity —O(1)
. While sorting the input isnlogn
, it doesn’t hurt the overall time complexity ofO(N²)
👌.
Three Sum Zero
Problem Statement: Are there elements a, b, c
in nums such that a + b + c = 0?
. Find all unique triplets in the array which gives the sum of zero
.
Note: The solution set must not contain duplicate triplets.
ExampleInput: nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]
Intuition
- Brute force — loop the array three times to check for possible candidates equal to zero.
- In every iteration — employ two sum solution of finding a number with it’s complement that add to the remainder off the iterated number.
- Sort it — remove the need to have a hashset to record previous seen compliments
Since we know how to implement the above intuitions as illustrated in the solution of Three Sum, we will only show the optimized solution.
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
result = set()
for i, num in enumerate(nums):
remaining_target = 0 - num
left, right = i + 1, len(nums) - 1
while left < right:
current_sum = nums[left] + nums[right]
if current_sum == remaining_target:
# a hashset can only have immutable keys
# hence adding tuple not list
result.add((num, nums[left], nums[right]))
left, right = left + 1, right - 1
elif current_sum < remaining_target:
left += 1
else:
right -= 1
return [list(triplet) for triplet in result]
Review *
- The time complexity —
O(N²)
, space complexity —O(N)
. The result set can contain uptoN//3
combinations hence leading to the overall space complexity to belinear
. - Takeaway — a hashset can only have immutable keys hence adding tuple, since list is mutable(
unhashable
).
Three Sum Smaller
Problem Statement: Given an array of n integers nums and an integer target, find the number of index triplets i, j, k
with 0 <= i < j < k < n
that satisfy the condition nums[i] + nums[j] + nums[k] < target
.
ExampleInput: nums = [-2, 0, 1, 3], target = 2
Output: 2
Explanation: There're two triplets with sums < 2: [-2, 0, 1], [-2, 0, 3]
Intuition
- Customise the previous used patterns to calculate all possible combinations when the inside
remainder sum
is less than the target as shown in the image below;
def threeSumSmaller(nums: list[int], target: int) -> int:
nums.sort()
ans, N = 0, len(nums)
for i in range(N):
left, right = i + 1, N - 1
rem_target = target - nums[i]
while left < right:
curr_sum = nums[left] + nums[right]
if curr_sum < rem_target:
ans += right - left
left += 1
else:
right -= 1
return ans
Review *
- The time complexity —
O(N²)
, space complexity —O(1)
. The explanation says it all 🤓.
Three Sum Closest
Problem Statement: Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
ExampleInput: nums = [-1, 2, 1, -4], target =1
Output: 2
Explanation: The sum closest to the target is 2. (-1 + 2 + 1 = 2)
Intuition
- Customise the previous used patterns keep track of the closest sum, bearing in mind that the closest can be to the left(
<-
) or right(->
) of the number line.
def threeSumClosest(nums: list[int], target: int) -> int:
nums.sort()
N, closest = len(nums), float('inf')
for i in range(N):
left, right = i + 1, N - 1
while left < right:
curr_sum = nums[i] + nums[left] + nums[right]
if abs(curr_sum - target) < abs(closest - target):
closest = curr_sum
elif curr_sum < target:
left += 1
else:
right -= 1
return closest
Review *
- The time complexity —
O(N²)
, space complexity —O(1)
. - Takeaway — closest can be of negative or positive diff hence using
abs
to compare which is closer to the target.
Conclusion
- All the three sum problems have commonalities with a few fine-tuning to solve particular use cases. It is only prudent to dissect the Two Sum Problems to clearly see the patterns extending to these solutions.
Note: The article cover image has not correlation to the problem and solutions provided.
References
- Three Sum Zero: Leetcode Link
- Three Sum Closet: Leetcode Link
- Three Sum Smaller: Leetcode Link
- Two Sum Less Than K: Leetcode Link
Series
- Prev << Leetcode: Sum Series — Two Sum
- Next >> Leetcode: Sum Series — Four Sum