6

Algo Problem Statement: Find the smallest array that adds up to the target sum.

Code Issue: I do not understand the difference in results when:

  • using the arr.push() method

vs.

  • using the Spread syntax

Please reference the comment line below.

The Spread syntax returns the correct solution, while the .push() method keeps on pushing onto the same array. I don't understand why it keeps referencing the same array in memory.

Many thanks in advance!

let howSum = (target, arr, memo = {}) => {
    if (target in memo) return memo[target];
    if (target === 0) return [];
    if (target < 0) return null;

    let smallest = null;

    for (let e of arr) {
        if (howSum(target - e, arr, memo) !== null) {
            let result = howSum(target - e, arr, memo);
            // result.push(e);
            result = [...result, e];

            if (smallest === null || result.length < smallest.length) {
                smallest = result;
            }
        }
    }

    memo[target] = smallest;
    return smallest;
};

console.log(howSum(10, [1, 2, 5])); // [5, 5]
Improve this question
4
  • 5
    result = [...result, e]; creates a new array. It's not due to using spread specifically, it's simply because result = [ ] assigns a new array to result. Commented Dec 17, 2020 at 23:38
  • 4
    Well, the answer to "I don't understand why it keeps referencing the same array in memory" is that it's by design. If used appropriately, there is a lot of utility in mutating objects instead of creating new ones. Commented Dec 17, 2020 at 23:43
  • @FelixKling, thank you. Can you elaborate a little more? The endgame is to update the array with the addition of a new element. Don't both methods accomplish updating the older array? I can either update the same array, or create a new array with the updated value. Commented Dec 17, 2020 at 23:51
  • 1
    I guess if you don't create a new array then every memo[target] entry refers to one and the same array, meaning the memoized solution for each target is exactly the same, which is obviously conceptually wrong. Commented Dec 18, 2020 at 0:13

2 Answers 2

Reset to default
11

array.push(element) vs. array = [...array, element]

Array.push adds an element to the end of the existing array while the spread syntax creates an entirely new array. For example, the following code will throw an error because we are trying to redefine a const:

const array = ["foo", "bar"];
array = [...array, "baz"]; // Uncaught TypeError: invalid assignment to const 'array'

Array.push adds to an existing array, so there is no need to redefine:

const array = ["foo", "bar"];
array.push("baz"); // No error; "baz" is successfully added to the end of the array.

Another difference is speed. array.push(element) is ~2,500 times faster than array = [...array, element];

As pointed out by @FelixKling, the spread syntax itself does not create a new array. You can also use the spread syntax in a function like this: myFunction(...myArray). This will use the array elements as arguments. So in other words, ...myArray will not create a new array, but [...myArray] will. Just a small detail worth noting.

Why your loop keeps referencing the same array in memory

The Spread syntax returns the correct solution, while the .push() method keeps on pushing onto the same array. I don't understand why it keeps referencing the same array in memory.

Objects in JavaScript (JavaScript arrays are objects) are reference types—not value types. Therefore, using the spread syntax, you create a new array (result), but still supply the old array (arr) to your function. When you use Array.push, you modify the array that was supplied to your function. And since you modify the array that was supplied (instead of creating a local one), you will keep calling your function with new values in the array. When you use the spread syntax, you create a new array (so result doesn't reference the arr array), and when you call your function with the arr parameter, you still have the same values as when you first called the function.

@trincot wrote a neat break down of what is going on in your code.

Here is an experiment you can do in a JavaScript console:

const myArray = ["foo", "bar"];

function changeArray(arrayParameter) {
  const arrayVariable = arrayParameter;
  // We are still referencing the array that was supplied to our function, so
  // although it looks like we tried to duplicate the array, arrayVariable.push,
  // arrayParameter.push, and myArray.push will all modify the same array.
  arrayVariable.push("baz");
}

changeArray(myArray);
console.log(myArray); // ["foo", "bar", "baz"]
Improve this answer
Sign up to request clarification or add additional context in comments.

9 Comments

Small correction: Spread syntax doesn't create the array. The array literal creates the array. But of course a spread element can only be used inside an array literal.
Thanks @Samuel Ebert, however isn’t the array a block scoped variable in the for loop? Thus being erased from memory on the next iteration?
@SamuelEbert thanks, so this goes back to the root of my confusion. If the “result” array gets erased on the next iteration, what’s causing its reference to stay “alive” and keep on being pushed elements instead of erasing and reinitializing itself? If you run the code and log the value of the result array, and run it again after swapping the commented line for the uncommented line under it, you’ll see what I mean. I’m assuming each iteration will redeclare the results array, but instead keeps referencing the original one. I deleted your last comment by mistake, but I did read it.
Okay this is embarrassing. I'm just very tired right now... So... I deleted my other comment like a second too quickly. Anyways, the array is a reference type. It won't work with "push" because you still reference the same array when you call the function in each iteration. So it does not get erased from memory, you just keep modifying the array that was supplied in the first call. So I'm sorry once again for the confusion, I'm not thinking clearly (I wasn't able to sleep this night due to insomnia). I'll read your code again when I've gotten some sleep. My mind is going all over the place.
@SamuelEbert Thank you for your answer, it helped me understand. I hope you get some rest, sir.
|
3

the .push() method keeps on pushing onto the same array. I don't understand why it keeps referencing the same array in memory.

If we take the variant of your code where you don't use the spread syntax, but push, then realise that:

  • push mutates the array, it doesn't create a new one
  • The only place where your code creates a new array is at return []

So, look at what happens after that return []:

  • result.push(e); will alter that array into [e].
  • The first time smallest is null, so smallest becomes a reference to that single array.
  • Another reference is made to that single array at memo[target]
  • This reference is returned to the caller, which assigns it to result.
  • A new value is pushed to that single array, which now has two elements. And here it comes:
  • As the above mentioned memo[target] references the same array as result, you have actually mutated that memo[target]: memo[target].length will now be 2.

This is undesired. Once you have assigned an array to memo it should never mutate. This is why at some point in your code you should make a new array.

Improve this answer

1 Comment

thank you for the step by step explanation. This makes sense. My flaw was that while I understood reference and value types, for some reason I assumed they behaved differently within the scope of a loop. Thanks again!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.