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] <= 100In #2899 Last Visited Integers, you process a sequence of operations that either add an integer or request a previously visited value using the keyword "prev". The key idea is to simulate the process while remembering the integers that have already appeared.
A common strategy is to maintain a dynamic list (or array) that stores all integers encountered so far. When a number appears, append it to the list and reset any counter related to consecutive "prev" queries. When the operation is "prev", increase a counter representing how far back you want to look in the list and return the corresponding element from the end if it exists; otherwise return -1.
This approach works because the list preserves insertion order, allowing efficient access to previously visited elements. Each operation is handled in constant time by indexing from the end of the list. Overall, the algorithm runs in O(n) time with O(n) extra space to store visited integers.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Array / Simulation with counter for consecutive "prev" operations | O(n) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
It is sufficient to implement what the description is stating.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Problems like Last Visited Integers are common in coding interviews because they test simulation skills and careful state tracking. While the exact question may not always appear, similar array and operation-processing problems are frequently asked.
The optimal approach is to simulate the operations using an array that stores all visited integers. When a "prev" operation appears, track how many consecutive "prev" queries have occurred and return the corresponding element from the end of the list. This allows constant-time access for each query.
A dynamic array or list is the most suitable data structure because it preserves the order of inserted integers and allows efficient indexing from the end. This makes it easy to retrieve previously visited elements when handling "prev" operations.
When a new number appears, it breaks the sequence of consecutive "prev" operations. Resetting the counter ensures that the next "prev" query starts from the most recently visited integer again, maintaining correct indexing behavior.