**Solution**

**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
```