Last Visited Integers

Difficulty: Easy | Acceptance: 62.30% | Paid: No Topics: Array, Simulation

You are given an array of strings words, where words[i] is either a digit string (0-9) or the string “prev”.

Starting with an empty array nums, for each string word in words:

• If word is a digit string, push the integer value of word onto nums.
• If word is “prev”, let k be the number of consecutive “prev” strings including the current one. Find the kth most recent element from nums. If k is greater than the size of nums, use -1 instead.

Return an integer array containing the answer for every “prev” string in words.

• Examples
• Constraints
• Simulation with Stack
• Array Indexing Approach

Examples

Example 1:

Input: words = ["1","2","prev","prev","prev"]
Output: [2,1,-1]
Explanation:
- "1" : Push 1 onto nums. nums = [1].
- "2" : Push 2 onto nums. nums = [1,2].
- "prev" : k = 1. The 1st most recent element is 2. Append 2 to answer.
- "prev" : k = 2. The 2nd most recent element is 1. Append 1 to answer.
- "prev" : k = 3. There are only 2 elements in nums. Append -1 to answer.

Example 2:

Input: words = ["1","prev","2","prev","prev"]
Output: [1,2,1]
Explanation:
- "1" : Push 1 onto nums. nums = [1].
- "prev" : k = 1. The 1st most recent element is 1. Append 1 to answer.
- "2" : Push 2 onto nums. nums = [1,2].
- "prev" : k = 1. The 1st most recent element is 2. Append 2 to answer.
- "prev" : k = 2. The 2nd most recent element is 1. Append 1 to answer.

Constraints

1 <= words.length <= 100
words[i] is either "prev" or a digit string from "0" to "9".

Simulation with Stack

Intuition Maintain a stack of seen integers and track consecutive “prev” occurrences to efficiently retrieve the kth most recent element.

Steps

• Initialize an empty stack to store seen integers and a counter for consecutive “prev” strings
• Iterate through each word in the input array
• If the word is a digit, convert it to an integer, push onto the stack, and reset the “prev” counter
• If the word is “prev”, increment the counter and check if we have enough elements in the stack
• Append the appropriate value (kth from end or -1) to the result array

class Solution:
    def lastVisitedIntegers(self, words: list[str]) -> list[int]:
        seen = []
        result = []
        prev_count = 0
        
        for word in words:
            if word == "prev":
                prev_count += 1
                if prev_count <= len(seen):
                    result.append(seen[-prev_count])
                else:
                    result.append(-1)
            else:
                prev_count = 0
                seen.append(int(word))
        
        return result

Complexity

• Time: O(n) where n is the length of words array
• Space: O(n) for storing seen integers and result
• Notes: Simple and intuitive approach with clear logic flow

Array Indexing Approach

Intuition Use array indexing directly instead of stack operations, treating the seen array as a dynamic list with index-based access.

Steps

• Create an array to store integer values and another for results
• Track the current position in the seen array and consecutive “prev” count
• For each word, either add the integer value or compute the index based on prev count
• Handle boundary cases where prev count exceeds available elements

class Solution:
    def lastVisitedIntegers(self, words: list[str]) -> list[int]:
        nums = []
        ans = []
        k = 0
        
        for word in words:
            if word == "prev":
                k += 1
                idx = len(nums) - k
                if idx >= 0:
                    ans.append(nums[idx])
                else:
                    ans.append(-1)
            else:
                k = 0
                nums.append(int(word))
        
        return ans

Complexity

• Time: O(n) where n is the length of words array
• Space: O(n) for storing nums and ans arrays
• Notes: Similar to stack approach but uses explicit index calculation for clarity