Triplets with a Given Sum
4 videos • 249 views • by Sprint Master This playlist comprises of 4 ways of solving the coding question, "Find triplets in an array that add up to a given sum". This is a very common Coding Interview question asked many times in Google , Amazon, Facebook, Microsoft, Apple and many other Big Tech companies. The 4 ways to solve this problem are 1. Brute-Force Approach - This is the basic way approach to find all triplets that can be formed from the array and check if any of the triplets add up to the given sum. The time complexity of this approach is O(n^3). 2. Using Binary Search - In this approach, we iterate over the array to find the first and second elements, and for the third element, we do a binary search which gives the expected sum. The time complexity of this approach is O(n^2logn). 3. Using Hashing - In this approach, we first pick an element from the array by iterating over the array. To find the rest of the elements, we use the Hashing approach using which we earlier solved "Find a pair with a given sum problem". The basic idea is to check if the complement of the element exists in the Hash Set. If it exists, then we found a pair. If the element doesn't exist, then the element is placed in the Hash Set. The time complexity of this approach is O(n^2). 4. Multiple Pointers with Binary Search - In this approach, we have two pointers one at the left end, one at the right end, and then search for the third element which can add up to the given up. The time complexity of this approach is O(nlogn). Resources: 1. Brute-Force Approach - https://bit.ly/3pD7iKh 2. Using Binary Search - https://bit.ly/3nXG80e 3. Using Hashing - https://bit.ly/2WVpoe3 The complete code samples for these approaches can also be found in the following links. Solution 1 - https://bit.ly/2WXPFZo Solution 2 - https://bit.ly/3o4nzHF Solution 3 - https://bit.ly/3n4bKQB