Strings vs Arrays in JS
Tags: algorithms, javascript, programming, stringsvsarrays
Published: 2023-03-04 13:56:31

Hey guys, recently I came across the ["Design a Text Editor" task on leetcode](https://leetcode.com/problems/design-a-text-editor/description/) (hard level). In short, we need to implement the following:
- Add text to where the cursor is
- Delete text from where the cursor is (simulating the backspace key)
- Move the cursor either left or right


**Rules for the code (as usual):**

1. Choose the right names for variables
2. Choose the right loop statements: for, while, forEach, reduce etc.
3. Avoid excess conditions and comparisons for edge cases
4. Escape the side effects in your algorithms function, because 
very often you need to do mutations to decrease space or time complexity

### Strings - version 1
The first thing that might come to mind is manipulating strings.

```js
class TextEditor {
  cursorPosition = 0;
  text = '';

  /**
   * @param {string} text
   * @return {void}
   */
  addText = (text) => {
    this.text =
      this.text.substring(0, this.cursorPosition) + text + this.text.substring(this.cursorPosition);
    this.cursorPosition += text.length;
  };

  /**
   * @param {number} k
   * @return {number}
   */
  deleteText = (k) => {
    const deletedCount = Math.min(this.cursorPosition, k);

    this.text =
      this.text.substring(0, this.cursorPosition - deletedCount) + this.text.substring(this.cursorPosition);
    this.cursorPosition = this.cursorPosition - deletedCount;

    return deletedCount;
  };

  /**
   * @param {number} k
   * @return {string}
   */
  cursorLeft = (k) => {
    this.cursorPosition = Math.max(0, this.cursorPosition - k);

    return this.text.substring(this.cursorPosition - 10, this.cursorPosition);
  };

  /**
   * @param {number} k
   * @return {string}
   */
  cursorRight = (k) => {
    this.cursorPosition = Math.min(this.text.length, this.cursorPosition + k);

    return this.text.substring(this.cursorPosition - 10, this.cursorPosition);
  };
}
```

Check it out on [leetcode](https://leetcode.com/problems/design-a-text-editor/submissions/895787782/).

Sometimes it fails by time limits. But will have a good spot by memory consumption.

<img src="https://gist.githubusercontent.com/mallchel/569354d0f5ed2270dddbfd073d130423/raw/2d9dde40da4af6f62b328cbe2c97a4e5d66a6e19/strings.png" alt="time-memory-chart" />



### Arrays - version 1
Looking at the best time-consuming solution, we will see code that manipulates arrays. And memory usage is good enough too.

<img src="https://gist.githubusercontent.com/mallchel/569354d0f5ed2270dddbfd073d130423/raw/ca19df457d5af09044f3ade0d338310e08604571/arrays.png" alt="best-time-memory-chart" />


Sample code:
```js
var TextEditor = function () {
  this.left = [];
  this.right = [];
};

TextEditor.prototype.addText = function (text) {
  for(var i = 0; i < text.length; i++) {
    this.left.push(text[i]);
  }
};
```


**Conclusion:** Big difference in time and almost nothing difference in memory. Why? Let's dive deep into the JS engine.

### JS engine
Firstly it depends on the amount of data, in our case we have <code>2 * 10<sup>4</sup></code> operations which is a lot. Also, it depends on the implementation of the JS engine.

**The `String`**
It is a primitive data type and as a rule, primitives are immutable, so strings don't change when the developer manipulates the strings. How it works:

```js
let text = 'string';
text += ' changed';
console.log(text);
```
In the console, we will see the `string changed` which means our `text` variable is mutable. But under the hood, the engine just creates a third empty string and copies the values of both strings to it, and assigns the result to the `text` variable. Therefore, we have mutable the `text` variable and immutable `string` data type.

Let's visualize this algorithm:

1. Create an empty range in memory for the new string.
To concatenate our two strings we need to save 14 chars (by 2 bytes).
<table>
  <td> _ </td>
  <td> _ </td>
  <td> _ </td>
  <td> _ </td>
  <td> _ </td>
  <td> _ </td>
  <td> _ </td>
  <td> _ </td>
  <td> _ </td>
  <td> _ </td>
  <td> _ </td>
  <td> _ </td>
  <td> _ </td>
  <td> _ </td>
</table>
2. Copy the first string
<table>
  <td>s</td>
  <td>t</td>
  <td>r</td>
  <td>i</td>
  <td>n</td>
  <td>g</td>
  <td> _ </td>
  <td> _ </td>
  <td> _ </td>
  <td> _ </td>
  <td> _ </td>
  <td> _ </td>
  <td> _ </td>
  <td> _ </td>
</table>
3. Copy the second string
<table>
  <td>s</td>
  <td>t</td>
  <td>r</td>
  <td>i</td>
  <td>n</td>
  <td>g</td>
  <td>  </td>
  <td> c </td>
  <td> h </td>
  <td> a </td>
  <td> n </td>
  <td> g </td>
  <td> e </td>
  <td> d </td>
</table>
4. Assign the result to the var
<table>
  <td>text = </td>
  <td>s</td>
  <td>t</td>
  <td>r</td>
  <td>i</td>
  <td>n</td>
  <td>g</td>
  <td>  </td>
  <td> c </td>
  <td> h </td>
  <td> a </td>
  <td> n </td>
  <td> g </td>
  <td> e </td>
  <td> d </td>
</table>
5. Frees memory that was used to hold `"string"` and `" changed"` strings.

As you see it takes additional operations than it really needs (it copies each string fully), and at some point in time we have two times more memory. Just open the console and paste the following code:

```js
let str = '';
console.time('experiment');

for (let index = 0; index < 100_000_000; index++) {
    str += 'w';
}

console.timeEnd('experiment');
console.log(str.length);
```

In my case, it took 9.5 sec. Now try to paste the following one:

```js
let str = [];
console.time('experiment');

for (let index = 0; index < 100_000_000; index++) {
    str.push('w');
}

console.timeEnd('experiment');
console.log(str.length);
```

In my case, it took 886 milliseconds 😃 great!
**Note:** This case is only appropriate for inserting in the end of the sequence and if you will try something like:
```js
let str = [];
console.time('experiment');

for (let index = 0; index < 500_000; index++) {
    const middleIndex = Math.floor(str.length / 2);
    str.splice(middleIndex, 0, 'w');
}

console.timeEnd('experiment');
console.log(str.length);
```
it will take a longer time than with strings 🤯.


**The `Array`**
It is happening because in "JS engines" the arrays are implemented like dynamic arrays. The ECMAScript standards don't strictly define how the arrays should work, and because of this, we may encounter different implementations in the JS engines. And also JS engines have different implementations for dense and sparse arrays. [Example in v8 for elements](https://v8.dev/blog/elements-kinds#packed-vs.-holey-kinds). And a few links about dynamic arrays:
[Dynamic Array (data structure)](https://www.interviewcake.com/concept/python/dynamic-array)
[How do Dynamic arrays work?](https://www.geeksforgeeks.org/how-do-dynamic-arrays-work)

Thus, in our case, array-based solutions will only be faster than string-based ones if only the `push` and `pop` methods are used. So it will look like manipulating two arrays.

```js
class TextEditor {
  left = [];
  right = [];

  /**
   * @param {string} text
   * @return {void}
   */
  addText = (text) => {
    this.left.push(...text);
  };

  /**
   * @param {number} count
   * @return {number}
   */
  deleteText = (count) => {
    let deletedCount = 0;

    while (this.left.length && deletedCount < count) {
      this.left.pop();
      deletedCount++;
    }

    return deletedCount;
  };

  /**
   * @param {number} movesCount
   * @param {'toLeft' | 'toRight'} direction
   */
  moveCursor = (movesCount, direction) => {
    let actualMoves = 0;
    let currentElement = null;
    let from;
    let to;

    if (direction === 'toLeft') {
      from = this.left;
      to = this.right;
    } else if (direction === 'toRight') {
      from = this.right;
      to = this.left;
    }

    while (from.length && actualMoves < movesCount) {
      currentElement = from.pop();
      to.push(currentElement);
      actualMoves++;
    }

    return this.left.slice(-10).join('');
  };

  /**
   * @param {number} movesCount
   * @return {string}
   */
  cursorLeft = (movesCount) => {
    return this.moveCursor(movesCount, 'toLeft');
  };

  /**
   * @param {number} movesCount
   * @return {string}
   */
  cursorRight = (movesCount) => {
    return this.moveCursor(movesCount, 'toRight');
  };
}

```

Check it out on [leetcode](https://leetcode.com/problems/design-a-text-editor/submissions/908878538/).


When we work with "big strings" that we decided to replace with the array we should remember the [limit for the range](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Errors/Invalid_array_length
). It is worth noticing that different algorithms exist to optimize manipulating strings and one of the most efficient is [rope](https://github.com/component/rope) by splitting strings into multiple smaller chunks.



Sources:
[ChatGPT](https://chat.openai.com/)
[Efficient string building in javascript](https://www.freecodecamp.org/news/efficient-string-building-in-javascript/)
[How Arrays are Implemented in JavaScript](https://medium.com/@kevinzifancheng/how-are-arrays-implemented-in-javascript-be925a7c8021)



Let me know your thoughts in the comment section below! 😊