Two Pointers 5 - Medium - 3 Sum - Java

Coding Interviews - 3 Sum (LeetCode)
This interview question is commonly asked by companies like Facebook, Microsoft, Amazon, Apple
First, we will 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==0. At this stage, our problem translates into finding a pair whose sum is equal to “−X” (as from the above equation Y+Z==−X).
Also we need to find all the unique triplets. To handle this, we have to skip any duplicate number. Since we will be sorting the array, so all the duplicate numbers will be next to each other and are easier to skip

Time Complexity -
Sorting the array will take O(N∗logN). The searchPair() function will take O(N). As we are calling searchPair() for every number in the input array, this means that 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.

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/