What's actually hard about solving leetcode style questions
Today I was working through the following problem:
Given an array of unsorted numbers, find all unique triplets in it that add up to zero.
Example 1:
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. smallest sum.'
Example 2:
Output: [[-5, 2, 3], [-2, -1, 3]]
Explanation: There are two unique triplets whose sum is equal to zero.
The hard part of solving a problem like this these days isn't finding a solution.
Like most problems, when I initially approached this, I was making it more complicated than it was. After a while of trying to come up with a solution, and accounting for what the problem had to do, I knew somewhere two pointers would have to be involved, and that solutions like calculating every single possible combination, and storing them in a hashmap to then check against my current target while looping through the array would be far too time inefficient to work in a practical setting. When going down such routes, I arrived at problems that would have to involve something like a nested for loop inside a nested for loop. Hardly ideal.
As it usually goes with these kinds of problems, I've found it's usually just a result of lacking something in your toolset that has long since been figured out already, and it's not really something you can figure out on your own. That being the case, I just looked at a trusted solution to get the right idea once I realized I must be missing something. Unfamiliar questions and looking at fresh code is confusing enough, but I know just to trust my brain and come back to it later. Sure enough, the next day I understood the problem and solutions much better. That isn't the hard part, though.
Obviously, just copying the solution would be foolish if the point is to improve our skills and thinking for solving these kinds of problems, so this is why I took my time to passively come to understand the problem and solution after getting optimal mental input from a working solution. It felt much easier after a day or two of mulling over the problem after dedicating a bit of time to reading through it and thinking about it and other working solutions.
The really hard problem for us is being able to explain how these solutions work, and figuring out how to apply them. The techniques have been figured out, but it's up to us to be able to implement them in our own way after we learn them from ingenious solutions figured out over time in the history of computer science by the giants upon whose shoulders we stand.
Remembering the logic is simple enough once you have thought about it enough and let your brain do its thing, but the real struggle is when you start the implementation and actually try to explain how every edge case is accounted for in the moment. You have to think many steps ahead, and this is very difficult to explain as you're going.
I also find that I come up with edge cases I didn't imagine once I start coding a little bit, once I know how to lay out the logic that must work, and that's the hardest part that usually stops me. It's not always explicitly stated how that solution you thought you understood accounts for edge cases you only think of once you get into the thick of coding. In this case, it was this line of code:
while (left < right && arr[left] === arr[left - 1]) {
left++; // skip same element to avoid duplicate triplets
}
while (left < right && arr[right] === arr[right + 1]) {
right--; // skip same element to avoid duplicate triplets
}
Full solution:
class Solution {
searchTriplets(arr) {
const triplets = [];
// TODO: Write your code here
// Sort the array
arr = arr.sort((a, b) => a - b);
// Loop through the array, skipping index if it's the same as the previous one
for (let i = 0; i < arr.length; i++) {
if (arr[i] === arr[i - 1]) continue;
// Use two pointers to to check every combo that adds up to the target that makes 0 with the current index
let target = -arr[i];
let left = i + 1;
let right = arr.length - 1;
while (left < right) {
const currentSum = arr[left] + arr[right];
if (currentSum === target) { // found the triplet
triplets.push([-target, arr[left], arr[right]]);
left++;
right--;
while (left < right && arr[left] === arr[left - 1]) {
left++; // skip same element to avoid duplicate triplets
}
while (left < right && arr[right] === arr[right + 1]) {
right--; // skip same element to avoid duplicate triplets
}
} else if (target > currentSum) {
left++; // we need a pair with a bigger sum
} else {
right--; // we need a pair with a smaller sum
}
}
}
return triplets;
}
}
This was a problem that I had foreseen while coding, and it actually stopped me in my tracks for a while. The only solution was to draw out an example array that had the situation I was imagining, which was something like this:
[-10, -10, 0, 3, 10, 20 , 30]
My thinking was, and something that was not explicitly explained in the solutions I read, wouldn't the code potentially skip over a valid triplet, because it was assuming that, because it had already seen the value before it, it must be a duplicate? In this example, when at a value of i = 0, I thought the code would then skip the left pointer up to 0, then move the right pointer down after not seeing a solution either way, and the left pointer would never go back down because it would always be equal to the value before it.
This point, once I walked through the problem, made me realize the brilliance of the order of the checks in the code. This situation was accounted for because before checking for duplicate entries, the while loop begins with checking the sum right away. It's something I thought of ahead of time, but something that was quite difficult to see until walking it through.
Personally, I think explaining this and solving these small problems within the problem is harder than understanding the core logic behind the solutions in the first place, and it's essential for demonstrating true skill. When you think of an edge case and you aren't sure how it's been accounted for when the code gets so lengthy, it's really hard to see without just walking through the problems.
What did I realize from all of this? The importance of test cases. This made me realize that I should probably open starting my problems with edge case test cases planned ahead of time so I can code and just check if my solution passes them. If the core logic is not barking up the wrong tree so to speak, it's probably just a small edit that will fix any points of failure. That gets me out of being stuck while I'm coding, because I have a way to test set aside ahead of time. The really hard part is realizing this and realizing those edge cases early, and not freezing when one hits you mid-code. That's what you really want to prevent, as it can be a really crushing feeling that inhibits you when you should just keep going.
I always knew writing test cases was a good practice, but this kind of thing has actually demonstrated to me why, and I only learned it by attempting problems myself.