Accepted + The Best Complexity: O(n) time / O(1) space. Well Explained JavaScript


  • 0

    Complexity:

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

    Live Demo

    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 ith iteration and just performed the operation of some type:

    • place the result of the operation to the ith 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-2th 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:

    1. indices 1 and 2 that form our pointer, mean that this is a pointer to index 0.
    2. 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.

    Live Demo

    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


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.