Three Number Sum

Three Number Sum Solution - Two Pointer Approach

1. We are going to two pointer approach to check if we meet the target. We are going to declare left and right pointers.
2. Since the array is not sorted, we are going to sort the array first.
3. Run an outer for loop till the length of the array.
4. Inside the for loop, declare two variables left = i+1 and right = length - 1
5. The current sum will be left + right + arr[i].
6. IF the current sum is equal to the target, push the triplets in a global array and continue the for loop and adjust left and right pointers accordingly.
7. IF currentSum is LESS THAN the targetSum - This means we can increment the left pointer and we might get a greater number, resulting in a greater currentSum which MIGHT be our target.
8. IF currentSum is GREATER THAN the targetSum - This means we can decrement the right pointer and we might get a lesser number, resulting in a lesser currentSum which MIGHT be our target.
9. Return the triplets global array at the end.

Time complexity

• O(nlogn) - sorting the array
• O(N^2) - For loop and while loop. Total: O(N^2)