Complexity:

- time: O(n)
- space: O(1)

This algorithm reuses free space of the input data structure to store pointers to previous items, thus works in-place to reducing the `space complexity`

.

The main idea is that after performing some operation, we store the result in place of `operation token`

:

```
[2, 1, '+'] -> [null, null, 3]
```

This means that after some operation performed, there always at least 2 items free before the operation token, we can reuse that space for implementing a pointer to previous items.

Just step back and imagine that we have a **linked list** instead of the array here, so after performing some operation we just remove nodes with `numbers`

that we've used in the operation from the list (`:`

is a pointer between nodes in linked list):

`24 : 2 : 3 : * : /`

-> `24 : 6 : /`

-> `4`

So when we meet operation token(`+`

/`-`

/`*`

,`/`

) we can just take `last two`

digits, in the **linked list** that's easy - we follow `pointer`

from the `operation token node`

to the previous node, from that node we follow to the previous node and eventually we find our 2 numbers for the operation.

The exact same idea is here. Just instead of using a **linked list** we use plain **array** and **use free space that is left after operations to implement pointer to the previous "node"**.

So if we are on `i`

th iteration and just performed the operation of some type:

- place the result of the operation to the
`i`

th index. - place the pointer to the previous "node" to the
`i-1`

index. The pointer will be a number that shows an`index`

of the previous item. `i-2`

th index stores the special token`<`

, which indicate that in the next index is the`pointer`

. Thus we use`<`

to indicate that the next`number`

is not just a plain`number`

but a`pointer`

to the previous node.

**Consider the next array:**

```
["-8","23","8","-","9","23","-","-","*"]
```

**1st operation**: We iterate thru the array until we meet operation token (`-`

), we perform `23`

`-`

`8`

operation, store the result `15`

(index `3`

) and make our pointer:

```
[-8, "<", 0, 15, "9", "23", "-", "-", "*"]
```

Note that:

- indices
`1`

and`2`

that form our pointer, mean that this is a pointer to index`0`

. - this pointer points to the
`index of number2 minus one`

.

**2nd operation**: We continue iterating thru the array and meet the next operation (`-`

), perform `9`

`-`

`23`

, store the result `-14`

(index `6`

) and make pointer (indices `4`

and `5`

):

```
[-8, "<", 0, 15, "<", 3, -14, "-", "*"]
```

**3rd operation**: We continue iterating thru the array and meet the next operation (`-`

).

We can find out the `first number`

for the operation - it always the item before the operation `-14`

(index `6`

which is `i-1`

). But the item before the `first number`

is a pointer - it is the number prefixed by the `<`

symbol. This means that we have to follow the pointer to index `3`

to finding the second number. After following the pointer, we get our `second number`

- `15`

, this is the first number that is not prefixed by the `<`

(it is prefixed by `0`

). Now we have 2 numbers, so can perform our operation `15 - (-14)`

and make the `new pointer`

:

```
[-8, "<", 0, null, null, "<", 2, 29, "*"]
```

Note that the pointer is equal to `2`

, that's because we actually use the `index`

of the `second number minus one`

for the pointers.

Also, that's a good illustration of another gotcha - to keep our time complexity linear `O(n)`

, we can't afford the `pointer chains`

, this will mean that we can spend a linear time to traverse the chain and this will ruin the time complexity of our algorithm.

Luckily, we can eliminate the `pointer chains`

in `O(1)`

time, so we are still in `O(n)`

budget. For that, when adding the `new pointer`

to the previous node, we simply check if that `new pointer`

points to other `pointer`

, if so, we just skip the intermediate one and the make the `new pointer`

point to the address of that middle one. This step is enough to prevent the creation of pointer chains. After adding this check, the result of the previous step will look like this:

```
[-8, null, null, null, null, "<", 0, 29, "*"]
```

Now, the last pointer points to the first item in the tokens array directly (indices `5`

and `6`

).

**4th operation**: The final step. We continue iterating thru the array and meet the next operation (`*`

). Here, we can just follow the `< 0`

pointer to get the `second number`

so we do so. After that we perform `-8`

`*`

`29`

operation and store the result `-232`

(last index):

```
[null, null, null, null, null, null, "<", -1, -232]
```

Now, we have iterated thru entire array so the result `-232`

is stored at the last index(index `8`

). Before the result, the pointer stored, it points out of the start bounds of the array (to `-1`

index).

As you can see, by reusing the free items of the array, we can use just `constant extra space O(1)`

and still, spend `linear time O(n)`

to correctly solve the computational problem. Of course, we have sacrificed the `stability`

of our algorithm - we mutate input data structure to store the pointers to previous items.

Entire code with comments:

```
/*
Function to check if variable holds an operation type.
@param {Any} Token.
@returns {Boolean} If token is string with operation type.
*/
var isOperation = function isNumber(token) {
// map of supported operations
var map = {
'+': true,
'-': true,
'*': true,
'/': true
}
return !!map[token];
};
/*
Function to check if variable holds a number.
@param {Any} Token.
@returns {Boolean} If token is of type of number.
*/
var isNumber = function isNumber(token) {
return (typeof token === 'number' && !isNaN(token));
}
/*
Function to perform operation with two numbers.
@param {String} Operation type.
@param {Number} Number 1.
@param {Number} Number 2.
@returns {Number} Result of performing the operation.
*/
var performOperation = function performOperation(operation, num1, num2) {
switch (operation) {
case '+': return num1 + num2;
case '-': return num1 - num2;
case '*': return ~~(num1 * num2);
case '/': return ~~(num1 / num2);
default: console.error('Unknown operation: ', operation);
}
};
/*
Function to set the pointer to the prevous item.
@param {Array} Array
@param {Integer} Index of the first item to nullify
@param {Integer} Index of the second item to nullify
*/
var nullifyPointer = function nullifyPointer(arr, index) { arr[index] = arr[index-1] = null; }
/*
Function to set the pointer to the prevous node.
@param {Array} tokens
@param {Integer} Index of result
@param {Integer} Index of second number
*/
var setPointer = function setPointer(tokens, i, number2Index) {
// pointer to previous node that we have found with `findIndex2`
var pointer = number2Index-1;
// check if pointer to previous node in fact points to another pointer
// if so collapse the intermediate pointer and nullify it
if (isNumber(tokens[pointer]) && tokens[pointer-1] === '<') {
tokens[i-1] = tokens[pointer];
nullifyPointer(tokens, pointer);
// if previous node is not pointer, point to it
} else { tokens[i-1] = pointer; }
// rise the `<` indicating that whis is a pointer
tokens[i-2] = '<';
}
/*
Function to find index of the second number by following the pointers to previous nodes.
@param {Array} Array of tokens to perform the search in.
@param {Integer} Start index for the search.
@returns {Ineger} The next suitable index.
*/
var findIndex2 = function findIndex2(arr, i) {
// If number has `<` before - this is a pointer - follow it.
if (arr[i-1] === '<') {
// follow the pointer
var pointer = arr[i];
// nullify the pointer
nullifyPointer(arr, i);
// set the pointer value to the result
return pointer;
// otherwise, - no `<` before, use it as second number
} else { return i; }
}
var evalRPN = function(tokens) {
for (var i = 0; i< tokens.length; i++) {
var token = tokens[i];
// if operation token - perform operation
if (isOperation(token)) {
// the first number is always next before operation token
var number1 = tokens[i-1];
// the second number could be behind pointer so perform jump to that pointer
var i2 = findIndex2(tokens, i-2);
var number2 = tokens[i2];
// get result of the operation
var result = performOperation(token, number2, number1);
// save the result to the current item - the place where the operation sit
tokens[i] = result;
// set pointer to null - optional step
tokens[i2] = null;
// set pointer to previous node
setPointer(tokens, i, i2);
// if not operation, just parse the number since it could be inside a string
} else { tokens[i] = parseInt(tokens[i], 10); }
}
// after the loop, - all items in the array will be null, and the result will sit at the end,
// just before the result will the pointer sit - it basically will point to the start of the array
// e.g. [null, null, null, '<', 5, 12]
// 12 - result
// `<`, 5 - pointer
return tokens[tokens.length-1];
};
```

Oleg Solomka @legomushroom 2016