Two Pointers 6 - Medium - 3 Sum Smaller - Java

Coding Interviews - 3 Sum Smaller (LeetCode)
This interview question is commonly asked by companies like Facebook, Microsoft, Amazon, Apple
This problem shares similarities with 3 Sum. The only difference is that, in this problem, we need to find the triplets whose sum is less than the given target. To meet the condition i != j != k we need to make sure that each number is not used more than once.

Following a similar approach, first we can sort the array and then iterate through it, taking one number at a time. Let’s say during our iteration we are at number ‘X’, so we need to find ‘Y’ and ‘Z’ such that X + Y + Z is less than target. At this stage, our problem translates into finding a pair whose sum is less than “target - X” (as from the above equation Y + Z == target - X).

Time Complexity -
Sorting the array will take O(N * logN). The searchPair() will take O(N). So, overall it will take O(N * logN + N^2), which is asymptotically equivalent to O(N^2).

Space Complexity -
Ignoring the space required for the output array, the space complexity of the above algorithm will be O(N) which is required for sorting if we are not using an in-place sorting algorithm.

Two pointer playlist
1. Two Sum 2-Input array is sorted - https://youtu.be/dNcK87v3z18
2. Remove Duplicates from Sorted Array - https://youtu.be/yXb4HgYLp2g
3. Squares of a Sorted Array - https://youtu.be/dRr9mLZyz_M
4. Dutch National Flag or Sort Colors - https://youtu.be/Ye48iT5YKpo
5. 3 Sum - https://youtu.be/6xg7ZGfhQdo
6. 3 Sum Smaller - https://youtu.be/VW0zTPMmv9Q
7. 4 Sum - https://youtu.be/co-St3w1mkw
8 . Shortest Unsorted Continuous Subarray - https://youtu.be/Cn4vPghVglU

Know more about me
LinkedIn - https://www.linkedin.com/in/umang-mavani/