Coding Challenges: How to Solve Them

Here you are going to see how to approach coding challenges like a pro and nail your next technical interview!

Preface

I wrote down everything that came to my mind while solving this challenge, until I arrived to a solution. In an interview setting, I would have done the same. This is how you want to practice for your coding challenges: as realistic as possible.

As you will see, there is no straightforward path to a solution. It’s unlikely that you’ll find the best approach from the beginning. Keep talking out loud, explaining your thought process as you explore different ideas.

I didn’t want to present just a solution to this problem. I wanted to recreate what went through my mind when I tried to solve it, to see also the approaches that didn’t arrive at anything meaningful, because this will happen in an interview. Just make sure you analyze them a bit before you start spending your precious time coding them.

Problem Statement

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Step 1 – Understand the Problem

The first thing you need to do is to make sure you fully understand the problem you’re going to solve. Get used to rephrasing coding challenges using your own words. It is essential to create a few examples, including edge cases: repeated elements, empty array, etc.

Example 1:

• Input: nums = [-1,2,1,-4], target = 1
• Output: 2
• Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Step 2 – Take Notes

Now we take note of the things that are relevant to this problem.

• We just need to return the closest sum.
• We do not care about the position in the array of the elements that make up the result. Therefore, we can sort the input and try to solve the problem from there. This is a very common approach.
• If the input has repeated elements, we can skip them to avoid computing the same triplet. For instance, the array nums = [-1,-1,0,1] is going to try the triplet (-1,0,1) twice. At this point, this looks like a micro-optimization though.

Step 3 – Brute Force

It is always a good first step to look for a brute force solution. If you’re in an interview, that will give you some points already and will make you feel confident.

For this problem, the brute force solution is very straightforward:

1. Generate all triplets.
2. Compute their sum.
3. Store the sum that is closest to the target.

In C++, we would have the following code:

This code is correct. However, its time complexity is O(n^3), for a vector nums of n elements, because of the three nested loops. Let’s see how we can improve this.

Step 4 – Optimize

Unfortunately, there isn’t a recipe to go from a brute-force to an optimal solution. Otherwise, it would be too easy! Sometimes this is more an art than a science, but here are some things worth trying:

• Finding the bottleneck(s). In this case, checking every single triplet.
• Trying a different data structure. If nothing comes to mind, go through the most common data structures in your mind and see if they’d help:
  • Stack
  • Queue
  • Different types of trees
  • Hash tables
  • Sets
  • Graphs
  • Etc
• Sorting the input.
• Solving a simpler version of the problem. What happens if we only had to take pairs of numbers, instead of triplets? If we can solve this for pairs, we can extend it to triplets very easily.
• Solving a more general version of the problem. This approach is common in dynamic programming. To see how to easily solve dynamic programming problems, be sure to check this article.
• A completely different approach. Sometimes, this is the best strategy to dramatically improve the performance of your code.

Let’s see if we can use the previous list to find a better solution.

Sorting the Input

We already mentioned in Step 2 that we do not care about the order of the input. Let’s see what happens if we sort it.

nums   = [-1, 2, -1, 1, 1, 2, 2, 2, -4, -4, -4, 1, -4], target = 1
sorted = [-4, -4, -4, -4, -1, -1, 1, 1, 1, 2, 2, 2, 2], target = 1

This problem is equivalent to this one, without all the duplicates:

sorted = [-4, -1, 1, 2], target = 1

With this, we have already reduced the size of our input, making the algorithm faster. We have added an extra O(n*log n) step. However the overall complexity for the average case is still O(n^3). It looks like we have not gained much but we might end up using this idea later.

Let’s add this little trick to our previous code.

We might have marginally improved the performance for the case where there are many duplicates. For the average case, this code could be even slower due to the extra sorting step and all the new if statements.

Let’s try another item from our list: simplification.

Simplifying The Problem

Let’s imagine we only need to find a pair whose sum is the closest to a given target. In this case, the brute force approach consist in computing the sum of all pairs, which will have a complexity of O(n^2).

We can also go through our previous list of things to try and see if it helps.

Sorting

I have already solved a variant of this problem in my article How to Learn Data Structures And Algorithms. I will summarize here the gist of the technique and write the code to solve the problem. Basically, we create two pointers:

• l, to the first element in the array – l is short for left.
• r, to the last element in the array – r is short for right.

The variable sum is initialized to nums[l] + nums[r]. We know that if we increment l, because the array is sorted, the sum will be equal or greater than the current sum. Similarly, if we decrease r, the sum will be equal or smaller to the current sum.

The only difference is that in this problem we need to store the sum that is closest to the target. The code for this is the following:

This algorithm has a complexity of O(n * log n), because of the sorting step. If the input is already sorted, the complexity reduces to O(n). Either way, this is better that the brute-force approach.

Back to the Original Problem

We have an optimized solution for a simpler version of our problem. Can we take advantage of it? Certainly. Let’s see how in our previous example.

nums = [-1,2,1,-4], target = 1

In our iteration, for every value of i, we can assume we take that element as the first element of the triple. Now, we just need to find the best solution in the rest of the array with a value of target - nums[i], because we already included nums[i] in our solution.

You might have already recognized here the twoSum problem we just solved!

If we put all this pieces together, we arrive at the following code:

Since we are sorting the input, we may as well skip over repeated elements.

The overall complexity of this algorithm is O(n * log n) + O(n * n) ~ O(n^2), which is an improvement of a factor of n over the brute force solution!

Conclusions

After reading this article you have seen how I approached this problem, the different ideas that I tried, what I discarded (or saved for later) and how I ended up putting the different pieces together to arrive at the solution.

This is not for you to copy my approach step-by-step. I hope you will learn a thing or two and get inspired to be able to come up with resources the next time you are trying to solve a problem.

Note: to find the original problem statement, visit this link.