SUM OF PAIRS (algorithm problem: stuck for a week)

SUM OF PAIRS (algorithm problem: stuck for a week)
0

#1

Well its a problem I found on codewar, and sharing it hear as stuck with it almost for a week and so close to solve this problem and really don’t want to give up now :worried: . Instruction for the problem is given below :

sum_pairs([11, 3, 7, 5],         10)
#              ^--^      3 + 7 = 10
== [3, 7]
`indent preformatted text by 4 spaces`
sum_pairs([4, 3, 2, 3, 4],         6)
#          ^-----^         4 + 2 = 6, indices: 0, 2 *
#             ^-----^      3 + 3 = 6, indices: 1, 3
#                ^-----^   2 + 4 = 6, indices: 2, 4
#  * entire pair is earlier, and therefore is the correct answer
== [4, 2]

sum_pairs([0, 0, -2, 3], 2)
#  there are no pairs of values that can be added to produce 2.
== None/nil/undefined (Based on the language)

sum_pairs([10, 5, 2, 3, 7, 5],         10)
#              ^-----------^   5 + 5 = 10, indices: 1, 5
#                    ^--^      3 + 7 = 10, indices: 3, 4 *
#  * entire pair is earlier, and therefore is the correct answer
== [3, 7]

NOTE: There will also be lists tested of lengths upwards of 10,000,000 elements. Be sure your code doesn’t time out.

Now, I solved the problem. But its timing out when it tested of lengths upwards of 10000000 elements. Its getting timed out. Here is my code

var sum_pairs = function(ints, s) {
    //your code here
    var film = [];
    var pair = [];

    for (var i = 0; i < ints.length; i++) {
        holder = s - ints[i];
        for (var j = 0; j < ints.length; j++) {
            if (holder == ints[j] && i !== j && i - j > 0) {
                var indices = i + j;
                var distance = i - j;
                film.push([distance, indices, [holder, ints[i]]]);
            };
        }
    }
    if (film.length == 0) {
        return film[1];
    } else {

        pair = film.sort(function(a, b) {
            return a[0] - b[0];
        });
        console.log(pair[0][2]);
        return pair[0][2];
    }
}

window.onload = function() {
    l1 = [1, 4, 8, 7, 3, 15];
    l2 = [1, -2, 3, 0, -6, 1];
    l3 = [20, -13, 40];
    l4 = [1, 2, 3, 4, 1, 0];
    l5 = [10, 5, 2, 3, 7, 5];
    l6 = [4, -2, 3, 3, 4];
    l7 = [0, 2, 0];
    l8 = [5, 9, 13, -3];
    sum_pairs(l5, 10);
}

I know I am running a double loop which is the reason for time out. But don’t see any other appropriate way to get this done. Please don’t give me any straight answer; as I really don’t want to spoil it (like I already found one on stackoverflow but they just posting the answer directly there, so I skip the whole topic :weary: ) So waiting for your feedback.


#2

I need some clarification: you only need to find the FIRST pair that sums to the number, right?

If so, why not break out of the loops as soon as you find the first pair?


#3

This looks interesting. Can you share a link to this challenge?


#4

NO, I don’t break. Rather I sort their distance after I get all the pair.


#5

https://www.codewars.com/kata/sum-of-pairs/train/javascript here is the link


#6

I managed to solve it, but I don’t think it’s any better that yours (my solution takes some 6 seconds (almost at the timeout!), with the four tests with large inputs taking ~2 seconds in total). My solution has no double loop, but it has a lot of transformations that use one-level loops and array function calls (with 1 for loop, 1 for loop inside an if-block, 4 function calls on the array, and a while-loop). I don’t think it can handle 10 million numbers (though I think the largest test only used half of that)

I went ahead and looked at how other people solved it and was stumped to see a really elegant solution which made my jaw drop. It’s 10 times faster than mine!


#7

@kevcomedia at least you pass the test. I think there is an algorithm to solve this issue. But rather we are using brute force to make it work. And what I hate about codewar is seeing other elegant answer. I admin that I do learn many things from there but it make me think “I SUCK AT CODING” :cry: .


#8

Well I guess we all start brute-forcing out solutions. I didn’t feel bad when I saw that solution (actually I was amazed and reminded me how much I don’t know), after seeing that the person who made that is a 1kyu and has solved more than a thousand katas.


#9

I will try to give you a hint, since you could always look up a solution, like you said.
For the following hint, my solution took 940ms to pass all the tests (I do not know how that compares with the other submitted solutions…).

This problem can be solved by making one pass through the array.

Knowing that, let’s say the array is [1, 4, 2, 5] and the desired sum is 3.
For each element, what would you do figure out if it can be paired?
For the first element, 1, you might say, the sum is 3 and I have a 1, so it would work out if there was a 2 in the array. Ok, I’ll keep that in mind, and let’s move forward to the next element (4).

The trick is in the “I’ll keep that in mind” - because when you hit the third element, 2, you would say… ok. for element of 2, it would work out if there was a 1 in the array because 3-1 = 2. Hey - didn’t I see a 1 before?

Hope this helps move you forward without giving it away. Reply back if you want another hint, good luck.


#10

Here’s an approach which has done wonders for me. Ask questions as you think through the problem and then answer those questions step-by-step. (The secret here I think is that in doing so you’re engaging the slow, deliberate, and logical part of your brain, “System 2”).

How could we state the problem simply?

Starting from the left and moving to the right, for each element we want to know if that element plus another element equals a number given as the 2nd argument. When we find the first pair that meets that criteria, return an array with those 2 values.

What’s a simple “naive” solution?

For every element, we can check every other element to see if we find a pair. We can do this with a pair of nested for loops. This would give us O(n^2) time complexity.

If we can improve on that, what’s the best possible solution we could find?

That would have to be O(n) since we may have to look at every element in the array of numbers in order to find our pair. At minimum we know that we may need to iterate over the entire array.

How can we look at every element in turn and keep track of what we’ve seen so we know when we find a pair?

We’ll have to have some way of storing what we’ve seen so far and accessing those stored values in constant O(1) time. For that we can use either an array with indexing or a hash map (Javascript object).

What should we store in our data structure as we look at each element in the array so we’ll know when we come across a match where a + b = n?

Spoiler Alert!

We know we’re looking for a total of a + b = n where a and b are elements in the array and n is the total given as the 2nd argument. That means that if we’ve seen a, we’re looking for a b such that n - a = b. We can store this value n - a in our data structure as we walk through the array. The first element we find that matches one of our stored values gives us the answer.


#11

I can’t imagine how that can be done with just one pass.

Say you have [1, 4, 1, 3, 2, 5], with 8 as the sum. First I’ll take 1, then since the sum is 8, it would work out if there was a 7 in the array. So with 1 in mind, you look for a 7, but fail. So you start again with 4, etc.

There’s also the problem of the “inner pair”, like [5, 3, 7, 5] with 10 as the sum. It should output [3, 7]


#12

Say you have [1, 4, 1, 3, 2, 5], with 8 as the sum. First I’ll take 1, then since the sum is 8, it would work out if there was a 7 in the array. So with 1 in mind, you look for a 7, but fail. So you start again with 4, etc.

So here is the next important bit. Yes, when you see a 1, ok, you don’t see a 7 yet, after all we just started traversing the array. But, if you could remember that you saw that 1, if later in the array you did see a 7, you’d be able to recall that you saw a 1, earlier.

In order to catch those “inner pairs” that you point out, you traverse the entire array, element by element. Just plug along and look at each value, checking with what has already passed by, and it will work out (this takes awhile to be convinced of! ).
To go to your second example, [5, 3, 7, 5] with 10 as the sum.
start walking the array:

  • You see a 5. Ok, if we end up seeing another 5, that would add up to 10. So remember that we saw a 5.
  • Next value is a 3. ok, well, if we’d seen a 7 already, we’d be done, but we haven’t seen a 7 yet, we’ve only seen a 5, and now we’ve seen this 3.
  • Next comes the 7. well, 10-7 is 3. HEY!!! we’ve seen a 3 before! So the answer is [3,7] and not [5,5] (which you would not detect until/unless you assessed that last 5 in the array).

Now it may look like I’m suggesting that you keep an array of “seen values” and then as you move along, iterate through that array looking for a match. But that’s just like double looping, and we are trying to beat the n^2 brute force solution.

So here is the big important hint (SPOILER): don’t use an array to keep track of what has been seen. Use a hash map (using {} ). The time difference in finding any “n” in a big array [1,2,3,…n…reallyBigNumber] versus finding bigHash[key] where you have a very large hash with lots and lots of keys is the difference between timing out and not timing out.

Using a hash or coming up with it as an idea is tricky the first time, and after that you know the trick.


#13

That’s exactly the killer solution I saw!

My solution actually used an object whose keys are numbers in the array (which I used to check if a number is in the array (faster than Array#includes() does I assume)), but I was too focused on an array-based solution.


#14

Thank you all for your valuable feedback. I think, I am gonna check out the hash thing you guys are talking about (really have no idea what it might be). Eventually whenever I pass test I will post my answer here to evaluate.


#15

@yuzu-r

In Javascript it’s just an object {}. A hash table or hash map is just a general term referring to a data structure that maps keys to values. That’s a term that spans across languages with different implementations.

In a Javascript object {} a key and value pair is referred to as a property and if the key of that property stores a function, then you can call it a method. Anything that’s not a primitive data type in Javascript is an object, meaning it has properties stored in key value pairs. So when we create an instance of an array and start calling array functions, we’re calling methods that belong to the array object (prototype).

Of course you can define your own objects and the most common way is to create one is var obj = {}; Then you can start adding your own properties. Definitely read the MDN guide Working with objects

@kevcomedia

Using an object definitely seems to be the way to go. You can use an array and achieve the same O(n) runtime if you know the range of the sums. Here’s what I mean. If for example, you know the range of the total and the individual elements in the array, you can initialize an array and use the indexes of the array to store what you’ve seen so far! in the solution below I picked the range of 0 to 99. Not the most common approach, but one that you sometimes see so another weapon in your arsenal.

Array lookups if you know the index are O(1). I noticed you don’t see this approach very often in Javascript and I would guess it’s because the underlying implementation of an array is actually… an object! Surprise! In other languages like C++, arrays are designed to allocate memory in a block and the values are stored sequentially in memory. This makes accessing them faster when compared to say a hash map where the memory address of keys and values are not necessarily next to each other.

Solution
function findFirstSumPair(arrayInput, numTotal) {

  if (arrayInput.length < 2) {
    throw new Error("Array must have at least 2 elements");
  }

  var arrayOfSeenValues = new Array(100).fill(false);

  for (let i = 0; i < arrayInput.length; i++) {

    let currValue = arrayInput[i];

    if (arrayOfSeenValues[currValue]) {
      return new Array(numTotal - currValue, currValue);
    }
    arrayOfSeenValues[numTotal - currValue] = true;
  }
  throw new Error("No pair found in array");
}

#16

Is this what you call memoization?


#17

Many thanks for sharing the info. And “Working with objects” is a great source to learn more about OOP. To be honest I am fairly new to coding and only able to grasp the procedural portion. OOP is way above my head right now. Can you suggest me any book about JS OOP which will have reference for real life working project and explanation? And I think I will be able to solve this KATA in this weekend as I was busy for the whole week for office work. And once again thanks for the sharing :smiley: .


#18

@kevcomedia

Memoization is a technique where you save the result of a function call so you can access the information again. If you see the same input, you can pull the saved result instead of having to call the function again. This saves processing time. It’s a common technique used in dynamic programming. Dynamic programming is where a solution is found from solving smaller subproblems. Take the fibonacci sequence where the a given number is the sum of two previous numbers. To get the nth number in the sequence:

var memo = {};

function getFibonacciNum(n) {

    if (n < 0) {
        throw new Error("Can't compute negative fib number");
    }        

    if (n === 1 || n === 0) {
        return n;
    }

    if (memo.hasOwnProperty(n)) {
        return memo[n];
    }
    var nthFibSum = getFibonacciNum(n - 1) + getFibonacciNum(n - 2);
    
    memo[n] = nthFibSum;
    
    return nthFibSum;
}

The memo object stores the result for n so we don’t duplicate function calls for a given n. There’s a great explanation on Interview Cake. It’s a tough concept so don’t worry if it takes some time to wrap your head around it.

@mitul036

There are a ton of good books out there. The ones on Amazon with many good reviews are probably good choices. I liked A Smarter Way to Learn Javascript. It’s basic in a good way - You get the core concepts without dumbing things down. You also learn how to interact with the DOM in plain Javascript. If I could go back and learn Javascript from the start, I would spend less time learning tools and frameworks, and more time on data structures, algorithms, and DOM interactions