A week of LeetCode (day 2/7)
I am glad to see you again in the Week of Leetcode series, carefully designed to help you stand out in the coding interview process, by providing a step-by-step analysis of 7 algorithmic tasks covering various topics and provoking critical thinking strategies that often show up in different technical interviews.
Coding interviews are necessary for getting a job in the tech industry and a must for FAANG, so get ready to ACE that coding interview.
Ready for today’s challenge? Let’s dive in!
Day 2: 3Sum
I will assume you haven’t read the task description, so here is a summary:
Given a sequence s of n numbers, return all unique triplets of numbers S[i], S[j] and S[k] such that:
i, j and k are distinct and S[i] + S[j] + S[k] = 0
Note: for the rest of this tutorial, I will assume WLOG that i < j < k, this assumption will make our life easier.
First Approach: Brute-Force
You may be tempted to go for a bruteforce-ish solution, that is to try all triplets and return those that satisfy the criteria, but this is not efficient. Let’s do some time complexity analysis for more details.
pseudo-code:
N = length of sequence S
result = []
for all i in [1,N]
for all j in [i+1,N]
for all k in [j+1,N]
if triplet(i,j,k) is good, then add it to resultWe have three nested loops, which means our solution is O(N³), in big-O notation.
In our case, n ≤ 3000, so N³ time is too much, we need to do better.
Hint: Try to reduce the problem to a simpler one. Let’s play with the equation and see.
s[i] + s[j] + s[k] = 0
The three numbers add up to 0, right? It follows that any two of them should be the same as the negative of the third one (so that they can even out the sum).
s[i] + s[j] = -s[k]
s[i] + s[k] = -s[j]
s[j] + s[k] = -s[i]
Now we have a slightly simpler problem, that is, if we fix the first element S[i], what are the pairs (S[j] , S[k]) with the condition that S[j] + S[k] = C (remember C = -S[i]).
The 2-Sum Problem:
I give you a sequence A and a target t, you give me all pairs of numbers (A[j], A[k]), such that A[j] + A[k] = t
But how can we solve that?
Let me remind (or introduce) you of the two-pointers technique.
The two-pointers technique is a way of solving array problems efficiently by ignoring unnecessary computations.
It begins by sorting the sequence and defining two-pointers (L and R for simplicity), initially L and R point to the first and last numbers of our sequence (respectively).
The left pointer L only moves to the right, and the Right pointer R only moves to the left, in a way that is more likely to give us our target number t.
This search technique ends once our two pointers meet. By then, it would find all the solutions.
Confused? let’s try an example.
Look at the following sequence.
Our target is to get all pairs that add up to 5 (t = 5)
First step: sort the sequence and define the two pointers.
First iteration L = 1
the algorithms know that the only way to decrease the sum to get it to 5 is by moving R to the left (since L only moves to the right, and moving L to the Right would increase our current sum).
So instead, it moves the right pointer to the left.
We still need to decrease the sum.
Cool, we found a pair that adds up to 5, so we add it to the result and keep moving the right pointer.
Now we need to stop and think for a moment, our sum now is less than the target 5, so moving the right pointer to the left makes little sense (since it only decreases the sum) so it is time to move our left pointer instead.
Again, we found a solution, add it to our solutions set, and move your right pointer.
We have found another solution, but it is the same as our previous solution (2,3), actually, for a fixed L all our solutions will be the same so we shouldn’t add it to our solutions set as we are looking for unique solutions.
Okay, let’s move our right pointer again.
Now that the two pointers meet, you have found all your solutions (double-check that there are no possible solutions we dismissed).
The skeptical reader may be tempted to think that it is still O(N²) since we have two nested loops, surprisingly, this turns out to be O(N), but why?
Notice that overall, the left Pointer only moves to the right and the right pointer only moves to the left, which is 2N steps and that is O(N), impressive!
pseudo-code of the two pointers technique to find t
t = targetN = length of sequence AL = 1
R = N
answer = []for all L in [1,N]
while L < R and A[L] + A[R] > t
decrease R by 1
if L >= R
terminate
if A[L] + A[R] == t
append the pair (A[L], A[R]) to the answer
keep moving R to the left until A[L] + A[R] < t
Back to our original problem, which we now have found a full solution for.
pseudo code
answer = []
N = length of the sequence Sfor i in [1,N]
run the 2-Sum algorithm on [i+1,N]
to find all pairs with sum -S[i] for all the pairs (j,k) found by the 2-Sum algorithm
add the triplet (i,j,k) to the answer
The overall complexity is O(N²)
Now that we have a solution on paper, let’s write some code!
My Python implementation:
My C++ implementation:
How we approached today’s task, and how to approach other challenges?
- Think about a naïve solution and build smarter ones upon it: we started by describing an O(N³) solution and kept improving it.
- Break the problem in your hand into smaller sub-problems: this technique is very useful, as smaller problems tend to have simpler and sometimes well-known solutions.
- Think about how to solve the smaller sub-problems efficiently and combine them into one final happy solution.
- Change the setting of the problem and make assumptions that help you better interpret the problem in front of you: notice that we sorted the original array in order to run the two-pointers algorithm, also we assumed (i < j < k) which changes nothing about the problem but it gives us the privilege of not thinking about the different orderings of the triplet.
- Reread this article many times until you fully appreciate it, especially if it is your first time to see the two-pointers technique.
Your Turn:
Congratulations! If you made it here in one sitting, I knew you could do it.
Now that you got some skills, Don’t stop here, put them into practice.
Go play with the code and write it by yourself from scratch, and challenge yourself to come up with applications of the two-pointers technique.
Bonus task: given a sequence S, Compute the number of pairs (i,j) with S[i] + S[j] ≤ X.
Use the two-pointers technique to come up with an O(N) solution.
Additional Problems for practice:
Count Number of Nice Subarrays
