If I do [a,b]=[b,a], am I modifying the array in-place with O(1) memory?

user_16855188 0
Viewed 82

Suppose I was given an array of character strings,

such as ['f', 'r', 'i', 'e', 'n', 'd'], and my task is to reverse it into ['d', 'n', 'e', 'i', 'r', 'f'].

I wrote the following JavaScript

var reverseString = function(s) {
    let h=0; let t= s.length-1;        
    while (h<t) {
        [s[h], s[t]] = [s[t], s[h]];
        h++; t--;
    }
};

So the trick I keep using in the while loop is [a,b]=[b,a].

How efficient is this in term of space complexity? Is there a better way you would write this in JS? Thank you

arrays javascript
2 Answers

Using an array literal and array destructuring assignment

[s[h], s[t]] = [s[t], s[h]];

is exactly as space- and time-efficient as using temporary variables

const a = s[t], b = s[h];
s[h] = a;
s[t] = b;

but probably quite a bit slower in actual execution because of all the overhead, at least until the compiler optimises away the array creation.

Either way, your reverseString method is O(n) (with n being s.length) and doesn't actually work for strings but only arrays.

user_10485720

Your implementation is n/2 since you're looping through half the list. Even though your loop is 1/2n it increases in a linear way as the size of the list increases. Therefore your implementation is O(n)

The answer to the most efficient way of reversing a list in javascript: What is the most efficient way to reverse an array in Javascript?

user_80095930
Related