Last Visited Integers - Video Solutions

Problem Overview: You receive a list of strings representing operations. A value can either be an integer or the string "prev". Every integer is recorded as a visited number. When you encounter "prev", return the k-th most recently visited integer where k equals how many consecutive "prev" operations have occurred since the last integer. If fewer than k integers exist, return -1. The task is essentially a stream simulation problem.

Approach 1: Using Two Stacks (O(n) time, O(n) space)

This approach explicitly models the operation history using two stacks. The first stack stores all integers seen so far. The second stack tracks results produced by consecutive "prev" calls. When a number appears, push it to the integer stack and clear the prev stack because the sequence of "prev" queries resets. When a "prev" operation appears, compute which previous element should be returned by referencing the integer stack index len(stack) - k. Push the returned value into the prev stack so the next "prev" automatically refers to the next older element. This method closely mirrors how the problem statement describes the behavior and is easy to reason about during interviews. Since each element is processed once, the total time complexity is O(n) with O(n) space to store visited integers. This technique fits naturally with problems involving history traversal and stack-like access patterns.

Approach 2: Using a Deque for Seen (O(n) time, O(n) space)

A cleaner simulation keeps all visited integers in a deque (or list) and tracks the current k value representing how many consecutive "prev" operations occurred. When an integer appears, append it to the deque and reset k = 0. When "prev" appears, increment k and check if the deque has at least k elements. If it does, return the element at index size - k; otherwise return -1. This approach avoids maintaining a second stack and relies on simple index lookup. The operations are constant time, so the full scan of the input array still runs in O(n) time with O(n) memory for the stored integers. It is a straightforward example of Array and Simulation working together with deque-style access patterns similar to a Stack.

Recommended for interviews: The deque/list simulation is typically the expected answer. It uses minimal state (a container plus a counter) and directly models the k-th previous lookup in constant time. Showing the stack-based reasoning first demonstrates understanding of the history behavior, while the optimized simulation highlights clean implementation skills.