[C++] State Machine Approach, 0ms, 23.5MB
This problem will require us to create a state machine that performs two different tasks:\n for numerical strings, it will store the number in a container;\n fo
This problem will require us to create a state machine that performs two different tasks:\n* for numerical strings, it will store the number in a container;\n* for `"prev"` strings, it will:\n    * if it is the first `"prev"` we meet, check when we last wrote in and take the last element and then write it down in our result variable;\n    * in all the other cases, it will take the `n`th last element we wrote in our container, with `n` being the number of consecutive `"prev"`s we encountered in a row.\n\nNow, to code our solution, let\'s get started with a few support variables:\n* `len` will store the size of `words`;\n* `pos` will be our pointer to know where to write in `res`;\n* `w` and `r` are going to be our write and read poitners, respectively;\n* `res` is going to be our result variable, initialised to be `len` elements already, to avoid reallocations.\n\nWe will loop through each `word` in `words` and handle two base cases:\n* if `word == "prev"`, we will:\n    * decrease `r` by `1`;\n    * compute a value that equals the `seen[r]` if `r >= 0`, `-1` otherwise;\n    * write said value in `res[pos]`;\n    * increase `pos` by `1`;\n* otherwise, we will:\n    * convert `word` to a number and store its value in `seen[w]`\n    * increase `w` by `1`;\n    * reset `r` to be `w`; \n\nAfter that, we can `resize` `res` to be only `pos` cells and finally `return` it :)\n\n# Complexity\n- Time complexity: $$O(n)$$\n- Space complexity: $$O(n)$$\n\n# Code\n```cpp\nclass Solution {\npublic:\n    vector<int> lastVisitedIntegers(vector<string> &words) {\n        // support variables\n        int len = words.size(), pos = 0, seen[len], w = 0, r = 0;\n        vector<int> res(len);\n        for (auto &word: words) {\n            // 1st case:\n            if (word == "prev") {\n                res[pos++] = (--r) >= 0 ? seen[r] : -1;\n            }\n            // 2nd case:\n            else {\n                seen[w++] = stoi(word);\n                r = w;\n            }\n        }\n        res.resize(pos);\n        return res;\n    }\n};\n```\n\nAn alternative way to write this would be by replacing `r` with a counter variable `cnt` that counts how many `"prev"`s in a row we have encountered.\n\nI like it a bit less since with it we will make one extra operation (`w - cnt`) per loop:\n\n```cpp\nclass Solution {\npublic:\n    vector<int> lastVisitedIntegers(vector<string> &words) {\n        // support variables\n        int len = words.size(), pos = 0, seen[len], w = 0, cnt = 0;\n        vector<int> res(len);\n        for (auto &word: words) {\n            // 1st case:\n            if (word == "prev") {\n                cnt++;\n                res[pos++] = w >= cnt ? seen[w - cnt] : -1;\n            }\n            // 2nd case:\n            else {\n                seen[w++] = stoi(word);\n                cnt = 0;\n            }\n        }\n        res.resize(pos);\n        return res;\n    }\n};\n```
['Array', 'C++']