Link: https://leetcode.com/problems/3sum-smaller/
Solution:
Topics: 3sum, 3sum closest, Two sum II
Intuition
Tricky little problem in the 3sum pattern, but its a good one. The key is to look for the target with the two pointer technique, and every time the value is smaller, we increase the result…but by how much?
The key insight here is understanding that if nums[i] + nums[l] + nums[r] < target , then ALL values for r between l (exclusive) and r (inclusive) would also create a triplet smaller than target. This is the case because in the 3sum pattern, nums is sorted.
For example:
target = 10
nums = [1,2,3,4,5,6]
[1,2,3,4,5,6]
^ ^ ^
i l r
nums[i] + nums[l] + nums[r] = 9
The total is less than 10, definitely we have found at least one triplet, but look closely at the values between l and r...
[1,2,3,4,5,6]
^ ^ - - - ^
i l r
If we shift the r pointer anywhere between r and l, the new triplet sum is guaranteed to be smaller than target (because nums is sorted).
So we need to add these newly formed triplets to the result. In this case there are 4 triplets to be added (r = 3,4,5,6)...
or simply r - l (5-1) = 4
Implementation
def 3sum_smaller(nums, target):
nums.sort()
res = 0
for i in range(len(nums)-2):
l = i + 1
r = len(nums) - 1
while l < r:
total = nums[i] + nums[l] + nums[r]
if total >= target:
r -= 1
else:
res += r - l
l += 1
return res
#time: o(n**2)
#memory: o(1)Review 1
I’m tagging this one hard because it took me a bit too long to get to the solution. I did realize that we had to do something with indices, but it wasn’t immediately clear to me how to proceed. The above editorial is great. The solution is so simple. Simply consider the fact that when total < target, all values for nums[r] where l < r <= curr_r will make a triplet less than total because nums is sorted. Its really that simple.