My Favorite Array Based Algo Question
A few years ago, I would have told you that I hated the interview process because I sucked at leetcode questions. My biggest qualm was that most of the time the question being asked is much harder than the actual responsibilities of the position but that was my headspace a few years ago.
I haven’t had to interview in a while and as I’m searching for jobs and getting interviews, I realized how much I actually matured. My code feels better, my solutions feel clever, and overall I can feel the growth. It was all put to the test recently as I’m getting ready for all scenarios of technical assessments. Whether it’s a take home or if it’s a live coding session — I’ve just been practicing DS and Algos and building side projects.
There’s a few patterns you’ll learn that can help you unfold some questions and I really like the Two Pointer Patter for arrays. It’s gotten me passed a few easy and medium level questions. One in particular is my favorite because I think about some of the things I’ve learned in mechanical engineering and almost flips it on it’s head. Let’s go check it out.
Given an array of unsorted numbers, find all unique triplets in it that add up to zero.
Input: [-3,0,1,2,-1,1,-2]
Output: [[-3,1,2], [-2,0,2], [-2,1,1], [-1,0,1]]
Explanation: There are four unique triplets whose sum is equal to zero.
When working with the two pointer pattern, you work with arrays that are sorted because it piggybacks off of the fact that your constraints will move either pointer. Going up or down a sorted array. If the array weren’t sorted, these constraints become a bit more difficult to express.
const searchTriplets = (arr) => {
let list = [];
// Sort the array for two pointer pattern
arr.sort((a,b) => a - b); //[-3,-2,-1,0,1,1,2]
}If we were to brute force this, we could potentially iterate through the array 3 times right? Once for every number inside a triplet but obviously we want to WOW ourselves and think like an engineer.
So this is what we’re going to do. What equation do we want/need? According the the prompt, the sum of the numbers of a triplet should equal 0 OR X+ Y + Z = 0.
Let’s iterate through the entire array once and for every iteration we’ll track arr[i] as targetSum, and declare two other variables. Left will be arr[i+1] and Right will be arr[arr.length — 1]. Essentially, we’ll track the current element of position i and use the two pointers to find the other two numbers that will give us 0.
Looking back at our equation, let’s turn the variables into code specific notation so that we can understand what’s going on.
arr[i] + arr[i+1] + arr[arr.length — 1] = 0;
If you remember from algebra, this equation is also the same as
arr[i+1] + arr[arr.length -1] = -arr[i]
So at i = 0, arr[i] = -3. arr[left] will start at -2 and arr[right] = 2. Given the equation above, we’d get -2 + 2 = 3 which is false. As we know it would give us 0 and therefore we need to update our pointers.
If the sum of arr[left] and arr[right] is less than -arr[i], the left pointer moves up one. If the sum is greater than -arr[i], the right pointer moves down. If it does equal -arr[i], then we’ve essentially found a triplet and we can push it to our list and also update our pointer.
const searchTriplets = (arr) => {
let list = [];
arr.sort((a,b) => a - b); //[-3,-2,-1,0,1,1,2]
for(let i = 0; i < arr.length; i++){
let targetSum = -arr[i];
let left = i + 1;
let right = arr.length - 1;
while(left < right){
let sum = arr[left] + arr[right];
if(sum < targetSum){
left++;
}else if(sum > targetSum){
right++
}else{
list.push([-targetSum, arr[left], arr[right]])
left++;
right--;
}
}
}
return list;
}Now as a beginner, looking at this code I’d get confused because you’re looking at variables instead of actual numbers. Feel free to print any variable of this function for better clarification but if you’re still struggling with it, do it pen an paper. Most times, I start most of these in pen and paper before typing away! I hope you found this problem enjoyable. As always — Happy coding!
