Solving a coding challenge
The picture you see up there is a Kata challenge from Codewars. I was fascinated by this challenge since it took me a few hours to complete. Here is how approached the problem, the challenges I met and ultimately, why I came up with my solution.
First, this is how I approached the problem. Let’s say I have an array of the following, [1, 4, 1, 3, 2, 5], and a single sum value 8. Now, our job is to find two numbers numbers in the given array that will sum up to the given sum 8.
An other detail is that we may have more than one pairs that sum up to 8 in the array, the right pair has to be the first in pair to have summed up to the given sum. For instance in this given array [5, 3, 7, 5] and the given sum of 10. The right pair to be returned is 3,7 and not 5,5 since 3,7 sum up to 10 before 5,5 does. Well this is the tricky part, but I will spare you from that detail for now. But I will come back to that when It can make more sense to you. Just bare with me.
Now to come up with an efficient solution, we need to think out of the box. Since to solve this problem we would be tempted to use double loops too keep track or a memory of the pairs that we have gone through while traversing the array. But if we take this approach, we will find our code running for more that 6 seconds which is gonna cause the compiler to time out for some lengthy input, besides, the Big O of such a solution is O(n²). Yes, this is extremely expensive to the processor for some a lengthy inputs.
Get Eric Malaba’s stories in your inbox
Join Medium for free to get updates from this writer.
So to considerably reduce the time complexity, We have to stop thinking about about using an array to keep the memory of the previous successful pairs. Instead, if we used an object instead, it changes the game. The big O for using an object becomes O(n) and the time complexity improves by 10 times. Yes 10 times, interesting right ? I know, so lets see how the solution looks like
const sum_pairs = (ints, s) => { const temp = {}; for(let i = 0; i < ints.length; i++) { if(temp[s — ints[i]] !== undefined) { return [s — ints[i], temp[s — ints[i]]] } temp[ints[i]] = s — ints[i]; }}
by using the object temp as we did, we keep the previously found values then what keep it with they ideal pair, then the next time we meet that ideal pair, the object will remember to have met its ideal pair before, then we return that pair; and if no matching pair is found, we return undefined.
Problems encountered
Coming up with this approach was not a cup of milk for me, as I said previously, It took me hours to crack. Here is the challenge I met. Well at first, I came up with a solution that was working and passed all the tests on Codewars, but when I submitted the solution, it returned an error that the execution has timed out. Well at first I was confused with this and didn’t understand what it means since my code was running in my computer. So I copied and and pasted the code in Google, then I learned that the problem was due to the fact that my algorithm too more than 6 seconds to execute, which caused the server to timeout.
Solution
After this insight from the internet, I realized that I was using nested loops to keep tracks of the previously met pairs. Besides the fact that this approach meant that the whole given array had to be traversed, it was very expensive time wise and space wise for the processor.
I had to rethink my approach if I were to reduce the time complexity of my algorithm. Then I thought about using objects instead of an array to keep track of the pair. I tried that as you can see in the solution above and it worked just like a charm. Besides, the time taken to run this was around 0.4 ms which more that ten times faster than the previous solution. I submitted my solution and moved to an other kata.
I hope this challenge was insightful for you as it was for me. It’s always good to keep your problem solving sharp by solving such challenges at least one or two of them every day. Happy hacking!!!
