Repeat Code With LeetCode: 3Sum

Photo by K8 on Unsplash. When I looked up “sum” on Unsplash, all I found was dim sum. I could caption this photo as “three dim sum,” but that would be wrong on a few levels.

You may notice that “Smack” will not make an appearance in this article — the two of us are in a bit of an argument. I think that a good way to learn is by making posts like this every week; he thinks that I should really prioritize studying, and only share things about coding interviews when I have more success. I think his argument is that I should pass a lot of coding interviews, then write on this blog when I am in a place of authority.

So let me be clear: I am not a FAANG engineer, or a coding guru, or some sort of mentor who learned the secret to coding interviews and wishes to enlighten my readers. I am just a guy working as a software engineer, and the negative backlash I received for one article motivated me to work through LeetCode and Cracking the Coding Interview problems publicly. I think that the LeetCode play button legitimizes my efforts, as it shows whether or not source code is efficient enough and accurate enough to pass…but not everyone would agree.

The 14 Coding Patterns

All of this is to say that I am not sure whether the Educative.io course in 14 patterns is the most effective way to study — but it is systematic, it is fairly popular in the industry now, and 3Sum is a pretty good, moderately difficult example of how the Two-Pointer Technique can be applied.

The Problem

Name: 3Sum

Difficulty: Medium

Topics covered: Two-Pointer Technique

Problem Description: Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

My solution is a pretty close C++ equivalent (*ahem* ripoff) of Nick White’s solution

My solution is here, and it is NOT hosted with ❤ on my personal GitHub link. One of these days I should learn to use Gist so I can stop using that stupid joke once and for all.

This is not an easy problem

I do not mean to stroke my own ego, but — and Nick White agrees with me on this — this problem is pretty hard because of the constraints they impose. If you are new to the Two-Pointer Technique, then Squares of a Sorted Array is a much better point of entry (and it is a LeetCode easy).

But what is the Two-Pointer Technique? It was covered a little bit in my String Compression post, but Smack satirically compared the Two-Pointer Technique to the “push-brakes-to-stop-car technique” because it seemed so obvious. Now it is starting to make a little more sense why it deserves its own name, as it is not always as obvious as it was in “string compression.”

For those of us who do not just have $60 a month lying around for Educative.io, and can only afford to read non paywall-blocked articles like this one, the 14 patterns are here. From the author of “14 Patterns” himself:

Two Pointers is a pattern where two pointers iterate through the data structure in tandem until one or both of the pointers hit a certain condition.Two Pointers is often useful when searching pairs in a sorted array or linked list; for example, when you have to compare each element of an array to its other elements.

Two pointers are needed because with just pointer, you would have to continually loop back through the array to find the answer. This back and forth with a single iterator is inefficient for time and space complexity — a concept referred to as asymptotic analysis. While the brute force or naive solution with 1 pointer would work, it will produce something along the lines of O(n²). In many cases, two pointers can help you find a solution with better space or runtime complexity.

Ways to identify when to use the Two Pointer method:

*It will feature problems where you deal with sorted arrays (or Linked Lists) and need to find a set of elements that fulfill certain constraints

*The set of elements in the array is a pair, a triplet, or even a subarray

Here are some problems that feature the Two Pointer pattern:

*Squaring a sorted array (easy)

*Triplets that sum to zero (medium)

*Comparing strings that contain backspaces (medium)
— Fahim ul Haq, emphasis mine

Lots of people say Two Sum is a good prerequisite for this problem, and I respectfully disagree…”squares of a sorted array” is better. You can solve Two Sum with a hashmap, and that kind of undermines the progression.

If you solve Two Sum with the Two Pointer Technique, then it is a great prerequisite. Try it for yourself, or check out a comprehensive illustrated guide here on Arslan Ahmad’s InterviewNoodle publication (it is not paywall blocked, and he founded DesignGurus).

The Solution

I needed a few things Nick White did not, and for that I am not sure if I would get the “Smack stamp of approval” if I ran this code by him. I had to check if the size was less than three, for example…if so, I just return an empty vector of vectors. A vector, if you are not a C++programmer, is the rough equivalent of a Java ArrayList.

To use the Two-Pointer Technique in this problem, the elements need to be sorted. std::sort is good to know…it does require an expensive O(n lg n) operation, but that is not a deal-breaker because the solution to this problem is less efficient than that. Nick White uses the Java equivalent of an automatic sort.

Line 13 sets boundaries in place to ensure that you skip duplicates. After that, this is the textbook Two-Pointer Technique. You work from the left, and from the right. Your goal is to obtain “target sum,” which is the value that “complements” another array value by summing to zero. Another way to think of this is that you have effectively reduced the problem to 2Sum. I have revisited this problem time and time again, and I was always confused when I heard that this problem “reduces to 2Sum.” I think this explanation makes more sense when you put it in the context of the Two Pointer Technique, and write that it “reduces to 2Sum if you solve 2Sum with the Two Pointer Technique.”

Yes, there are solutions that use a hashmap for 3Sum…but it is way more common to do it Nick White’s way. Educative.io follows a similar approach, and so do most of the top-voted LeetCode solutions.

Lines 30–37 are also for skipping over duplicates. Lines 39–46 fall again into textbook Two-Pointer Technique code. If the sum is lower than the target, move your left pointer right. If the sum is higher than the target, move your right pointer left. I think the Two Pointer Technique would be way easier to understand if everyone called it the Two Index Technique, since “pointer” evokes images of C++ specific code, but that is neither here nor there.

Here is a very well-illustrated guide to the Two-Pointer Technique. I take issue with how it “confuses” the Two-Pointer Technique with Fast and Slow Pointers, but “confuses” is in quotes because the 14 Coding Patterns are not really a universal term. My understanding is that they were made up by someone who wanted to do coding interview coaching.

Closing Thoughts

Studying for coding interviews is, in a word, overwhelming. Some people are quite good at it, though, and a couple of people who are very good at it said they did so many medium problems that they began to recognize patterns.

“14 Coding Patterns” is just one way to consolidate these patterns. You can find LeetCode mappings here, if you are more interested in just tackling problems and looking up tutorials as needed instead of paying for the one-stop shop Educative.io provides in the somewhat expensive course everyone is on about.

No matter what approach you choose, learning takes time. Yes, some people are geniuses. Some people can breeze through this. For the rest of us, you need to work these problems, understand the solutions, make some leaps, and continue to practice. Practice is what all these coding interview courses have in common, similar to how no reputable SAT course would come without practice questions, and no effective Security+ course would not have practice simulations. But the SAT and Security+ exam are a lot of vocabulary and memorization…this is like a cross between linguistics and math.

So I need to acknowledge that the person I am arguing with had a point. I never passed the Google interview. I do not teach my own class. I do not have a long list of everyone who landed FAANG jobs because they went through my course. Design Gurus and some of the popular tech channels you can find for free on YouTube do.

But if you search for resources in your coding interview studies, what will you find? There are fantastic YouTube channels like Nick White’s. There are some free articles on HackerNoon and FreeCodeCamp, but not enough in my opinion. There are lots and lots of articles on Medium, behind a paywall, and incredible things like Educative.io that cost money.

I would like to do my part to fill in the gap. If you want to read something by an industry guru, try Cracking the Coding Interview or Educative.io.