3Sum Smaller https://leetcode.com/problems/3sum-smaller/
- Brute force is N^3 and N^2 is the optimized algorithm which uses two pointer technique.
- Look at the analysis for https://leetcode.com/problems/3sum-closest/. Understand how the two pointer scheme works and why we move j to the right and k to the left. The intuition is that based on the comparision with target sum, we can skip portions.
- A great explanation is available here: https://leetcode.com/articles/3sum-smaller/. First reduce the problem to 2SUM and then apply binary search or 2 pointer solution.
- In binary search, the 2 SUM condition is nums[i]+nums[j] < target. This means we want to find all the nums[j] which satisfy nums[j] < target-nums[i]. This means we want to find the rank of target-nums[i]. use the code for rank from notes.
- Once you understand that well, there is one line of code required to make this work.
while j < k: if nums[i]+nums[j]+nums[k] < target: triplets = triplets + (k-j)
class Solution(object): def threeSumSmaller(self, nums, target): """ :type nums: List[int] :type target: int :rtype: int """ nums.sort() triplets = 0 for i in range(len(nums)): j,k = i+1, len(nums)-1 while j < k: if nums[i]+nums[j]+nums[k] < target: triplets = triplets + (k-j) j = j+1 else: k = k-1 return triplets