Is the space complexity O(1) or O(N) for the following code snippet?

Shahid Umar 0
Viewed 58

This is one of the leetcode problems. In this problem we are to build an array from permutation and the challenge is to solve the problem in O(1) space complexity, so does the solution fulfills the criteria or not? One more thing if we are manipulating the same array but increasing its length by appending the elements at the end, does it mean that we are assigning new space hence causing O(N) space complexity during the execution of the program?

var buildArray = function(nums) {
        let len = nums.length
        for (let i = 0; i < len; i++) {
           nums.push(nums[nums[i]]); 
        }
        nums = nums.splice(len, nums.length);
        return nums;
    };
space-complexity arrays javascript
3 Answers

This is O(n) space complexity, you can't "cheat" by pushing your data on the input array, because you are using extra space anyways.

This code would be the equivalent of storing your data in a new array, and then returning that

I would guess the target of this space complexity limitation is for you to reach to a solution using pointers to mutate the input array

Aramil Rey0

The space complexity still is O(n). The input array has n length. When you push in the array it basically allocates one more memory location and then update the array. By pushing the elements in the array you are still using extra n space.

In C++, to resize the array code would be written as:

int* arr = new int[10]
int* resize_arr = new int[size*2];
for(int i = 0; i < size; i++)
    resize_arr[i] = arr[i];

arr = resize_arr;
delete[] resize_arr;

after using all the allocated space, to add more elements you need to create a new array then copy the elements.

All these steps are done in one line in python. It does not mean you are not using more space.

Lunar Evans0

Since for any given nums you are looping at least once the entire array and then do an O(1) operations ( keys lookup & push ), it would be safe to say this is an O(n) solution.

MKougiouris0
Related