2

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

Mister Jojo
  • 20,093
  • 6
  • 21
  • 40
Yani
  • 35
  • 4
  • 5
    the most efficient way is to use `Array.reverse()` – Mister Jojo Sep 17 '21 at 23:45
  • 1
    The specific assignment is constant memory, yes (the overall Big-O complexity relates to the loop itself). A better question might be if JS implementations (are required to) optimize such structuring assignment, or if a temporary array is created on the RHS. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Destructuring_assignment – user2864740 Sep 17 '21 at 23:47
  • 3
    If you're not trying to modify an array with thousands and thousands of entries, it does not matter. – Pointy Sep 17 '21 at 23:48
  • Why not just use a temporary value anyway? That's normally how you'd do it. I'd just use `Array.reverse()`, but a naive way would be `let sh = s[h]; s[h] = s[t]; s[t] = sh;`, and it should be better than your above code. – Alex Huszagh Sep 17 '21 at 23:52
  • 1
    PS: the implementation of `Array.reverse()` does not move anything in memory (it only changes the reading direction) – Mister Jojo Sep 17 '21 at 23:52
  • @MisterJojo I tried to avoid using ```reverse()``` for the purpose of my exercise, but thanks it's good to know that method does not move anything in mem – Yani Sep 18 '21 at 00:01
  • @MisterJojo do you mean `someArray.reverse()`? There is no static `Array.reverse` method. Also what makes you assume it doesn't modify the array? JS arrays don't have a "reading direction". – Bergi Sep 18 '21 at 00:02
  • 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) – Nicholas Bergesen Sep 18 '21 at 00:06
  • @Bergi I mean https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/reverse -- and if I wrote a meaning of reading it is to give an image. Are you expecting a course on [stack](https://en.wikipedia.org/wiki/Stack_(abstract_data_type)) management in a simple commentary ? – Mister Jojo Sep 18 '21 at 00:18
  • @MisterJojo Maybe you gave me the wrong image then :-) The native array `.reverse()` method certainly does move things around in memory, it touches every array element once. – Bergi Sep 18 '21 at 00:20
  • @Bergi no, the elements are not moved in memory, the stack of their pointers does not move either, there is just the value of the increment which changes sign and the pointer on the first element go pointing on the last. – Mister Jojo Sep 18 '21 at 00:26
  • @MisterJojo What makes you assume that js arrays are implemented as stacks? They are not. – Bergi Sep 18 '21 at 00:28
  • @Bergi Ok, let's admit this hypothesis, how do you think arrays are implemented in JavaScript, knowing that stack technology is one of the pillars of computing and that these algorithms have been extensively tested for decades? – Mister Jojo Sep 18 '21 at 00:36
  • @MisterJojo No relation to battery technology, they're just basic [dynamic arrays](https://en.wikipedia.org/wiki/Dynamic_array). See e.g. https://itnext.io/v8-deep-dives-understanding-array-internals-5b17d7a28ecchttps://stackoverflow.com/q/11514308 https://stackoverflow.com/q/9233814 https://stackoverflow.com/q/43855875 https://stackoverflow.com/q/8423493 for references (although some of these are quite old, and the implementation may change). I've never heard of any trickery to flip iteration order. – Bergi Sep 18 '21 at 00:47

2 Answers2

1

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.

Bergi
  • 630,263
  • 148
  • 957
  • 1,375
  • Yes I understand it only works for array. Thanks for explaining the efficiency part – Yani Sep 18 '21 at 00:12
0

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?

Nicholas Bergesen
  • 303
  • 2
  • 12