Home > Back-end >  Subsets leetcode - Pushing into arr seems to be incorrectly pushing into wrong indexes
Subsets leetcode - Pushing into arr seems to be incorrectly pushing into wrong indexes

Time:10-08

Was working on this leetcode question: https://leetcode.com/problems/subsets/

and came up with this solution:

INPUT = [1, 2, 3]


var subsets = function(nums) {
    
    let ans = []
    
    for (let num of nums) {
        
        // DUPLICATE ARRAY
        ans = [...ans, ...ans]
        const size = ans.length
        
        // ITERATE THROUGH LAST HALF OF ARR
        for (let i = size / 2; i < size; i  ) {
            ans[i].push(num) <------------- THIS AINT RIGHT :(
        }
        
        ans.push([num])
    }
    
    return [[], ...ans]
};

ANS = [[],[1,2,3,3],[1,2,3,3],[2,3],[1,2,3,3],[1,2,3,3],[2,3],[3]] (INCORRECT)

However, it seemed to be incorrectly pushing values in multiple indexes for some reason. After fiddling around with the code thinking my logic is correct, I came up with this:

var subsets = function(nums) {
    
    let ans = []
    
    for (let num of nums) {
        
        // DUPLICATE ARRAY
        ans = [...ans, ...ans]
        const size = ans.length
        
        for (let i = size / 2; i < size; i  ) {
            ans[i] = [...ans[i], num] <--------------- THIS WORKS
        }
        
        ans.push([num])
    }
    
    return [[], ...ans]
};


ANS = [[],[1],[1,2],[2],[1,3],[1,2,3],[2,3],[3]] (correct)

And that ended up working... Why is this happening? Doesn't arr[i].push(num) pretty much equal the same thing as arr[i] = [...arr[i], num]

CodePudding user response:

The reason is that the subarrays are not copied when you do:

    ans = [...ans, ...ans]

This merely produces the same subarray references. This means that when you push unto one of the subarrays in the second half of ans, you'll see the effect also via the first half of ans, as both halves reference the same subarrays.

So to solve this, make a deeper copy when producing the second half:

    ans = [...ans, ...ans.map(arr => Array.from(arr))]

The second, working version, performs this deeper copy in the line that you marked.

  • Related