Given an integer array nums where nums[i] is either a positive integer or -1. We need to find for each -1 the respective positive integer, which we call the last visited integer.
To achieve this goal, let's define two empty arrays: seen and ans.
Start iterating from the beginning of the array nums.
seen.-1 is encountered, let k be the number of consecutive -1s seen so far (including the current -1),
k is less than or equal to the length of seen, append the k-th element of seen to ans.k is strictly greater than the length of seen, append -1 to ans.Return the array ans.
Example 1:
Input: nums = [1,2,-1,-1,-1]
Output: [2,1,-1]
Explanation:
Start with seen = [] and ans = [].
nums[0]: The first element in nums is 1. We prepend it to the front of seen. Now, seen == [1].nums[1]: The next element is 2. We prepend it to the front of seen. Now, seen == [2, 1].nums[2]: The next element is -1. This is the first occurrence of -1, so k == 1. We look for the first element in seen. We append 2 to ans. Now, ans == [2].nums[3]: Another -1. This is the second consecutive -1, so k == 2. The second element in seen is 1, so we append 1 to ans. Now, ans == [2, 1].nums[4]: Another -1, the third in a row, making k = 3. However, seen only has two elements ([2, 1]). Since k is greater than the number of elements in seen, we append -1 to ans. Finally, ans == [2, 1, -1].Example 2:
Input: nums = [1,-1,2,-1,-1]
Output: [1,2,1]
Explanation:
Start with seen = [] and ans = [].
nums[0]: The first element in nums is 1. We prepend it to the front of seen. Now, seen == [1].nums[1]: The next element is -1. This is the first occurrence of -1, so k == 1. We look for the first element in seen, which is 1. Append 1 to ans. Now, ans == [1].nums[2]: The next element is 2. Prepend this to the front of seen. Now, seen == [2, 1].nums[3]: The next element is -1. This -1 is not consecutive to the first -1 since 2 was in between. Thus, k resets to 1. The first element in seen is 2, so append 2 to ans. Now, ans == [1, 2].nums[4]: Another -1. This is consecutive to the previous -1, so k == 2. The second element in seen is 1, append 1 to ans. Finally, ans == [1, 2, 1].
Constraints:
1 <= nums.length <= 100nums[i] == -1 or 1 <= nums[i] <= 100Problem 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.
In this approach, we utilize two data structures: a stack to maintain the current viewed positive integers and another to handle queries simulated by -1. While iterating through the array, maintain the stack for positive integers. For each -1 encountered, manage a counter to handle consecutive -1s and respond accordingly by peeking into the positive stack.
The function last_visited_integers_stack implements the logic of maintaining a stack (list) seen for positive integers in reverse order and a counter to track consecutive -1 occurrences. When a -1 is read, based on the historical positive numbers and the count of consecutive -1, it appends the correct element to the result list or -1 when not enough past positives exist.
Time Complexity: O(n), where n is the length of the input list nums, as we traverse the list once.
Space Complexity: O(n), as we maintain potential elements for the seen stack and answer list.
This approach optimizes the storage and retrieval of last visited elements using a double-ended queue (deque). This structure allows appending to the front and accessing elements by index efficiently. While iterating through the array, prepend new positive integers, and resolve -1 elements by determining their position against the sequence recorded in the deque.
The function lastVisitedIntegersDeque leverages an array seen that acts like a deque by frequently adjusting with unshift to manage positive integers, akin to prepending to a list. It counts consecutive -1s and efficiently accesses the required past seen integers, yielding results in the array ans based on consecutive -1 conditions.
JavaScript
Java
Time Complexity: O(n) as we iterate through each element of nums once.
Space Complexity: O(n) for storing the seen deque structure.
| Approach | Complexity |
|---|---|
| Approach 1: Using Two Stacks | Time Complexity: Space Complexity: |
| Approach 2: Using a Deque for Seen | Time Complexity: Space Complexity: |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Stacks | O(n) | O(n) | When you want an explicit representation of history traversal and consecutive prev queries. |
| Deque/List Simulation | O(n) | O(n) | Best general solution. Minimal logic with constant-time lookup for the k-th last visited value. |
How to EASILY solve LeetCode problems • NeetCode • 427,739 views views
Watch 9 more video solutions →Practice Last Visited Integers with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor