Skip to main content
Talentd

Last Visited Integers - Solution & Explanation

EasyArraySimulation14 min read
Practice this problem

Problem Statement

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.

  • If a positive integer is encountered, prepend it to the front of seen.
  • If -1 is encountered, let k be the number of consecutive -1s seen so far (including the current -1),
    • If k is less than or equal to the length of seen, append the k-th element of seen to ans.
    • If 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 = [].

  1. Process nums[0]: The first element in nums is 1. We prepend it to the front of seen. Now, seen == [1].
  2. Process nums[1]: The next element is 2. We prepend it to the front of seen. Now, seen == [2, 1].
  3. Process 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].
  4. Process 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].
  5. Process 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 = [].

  1. Process nums[0]: The first element in nums is 1. We prepend it to the front of seen. Now, seen == [1].
  2. Process 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].
  3. Process nums[2]: The next element is 2. Prepend this to the front of seen. Now, seen == [2, 1].
  4. Process 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].
  5. Process 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 <= 100
  • nums[i] == -1 or 1 <= nums[i] <= 100

Approach Overview

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.

Approach 1: Approach 1: Using Two Stacks

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.

Code

PythonC

Python

C

Complexity

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.

Try this approach in the editor →

Approach 2: Approach 2: Using a Deque for Seen

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.

Code

JavaScriptJava

JavaScript

Java

Complexity

Time Complexity: O(n) as we iterate through each element of nums once.

Space Complexity: O(n) for storing the seen deque structure.

Try this approach in the editor →

Approach 3: Simulation

We directly simulate according to the problem description.

Define an array seen to store the positive integers we have encountered, and an array ans to store the answer. We also need a variable k to record the number of consecutive -1s.

We traverse the array nums:

  • If the current element x = -1, we increment k by 1. If k is greater than the length of seen, we append -1 to ans; otherwise, we append the k-th element from the end of seen to ans.
  • If the current element x is a positive integer, we reset k to 0 and append x to the end of seen.

The time complexity is O(n) and the space complexity is O(n), where n is the length of the array nums.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Using Two Stacks

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.

Approach 2: Using a Deque for Seen

Time Complexity: O(n) as we iterate through each element of nums once.

Space Complexity: O(n) for storing the seen deque structure.

Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Two StacksO(n)O(n)When you want an explicit representation of history traversal and consecutive prev queries.
Deque/List SimulationO(n)O(n)Best general solution. Minimal logic with constant-time lookup for the k-th last visited value.

Video Solution

Leetcode BiWeekly contest 115 - Easy - Last Visited Integers • Prakhar Agrawal • 1,022 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Last Visited Integers easy or hard?
Last Visited Integers is classified as an Easy problem on LeetCode with an acceptance rate above 60%. The main challenge is correctly tracking consecutive "prev" queries and mapping them to the k-th previously seen integer.
Last Visited Integers Python/Java solution
In Python, a list is usually used to store visited integers and access elements using negative indexing. In Java, an ArrayList or ArrayDeque works well for maintaining the sequence and retrieving elements using size-based indexing.
How to solve Last Visited Integers in O(n)?
Iterate through the operations array while storing every integer in a list. Maintain a counter k that increments for each "prev" query and resets when a new integer appears. For each "prev", return nums[len(nums) - k] if the index exists; otherwise return -1. This single pass guarantees O(n) time.
What is the best approach for Last Visited Integers?
The most practical approach stores all visited integers in a list or deque and tracks the number of consecutive "prev" queries using a counter k. Each "prev" returns the element at index size - k if it exists. This simulation runs in O(n) time and O(n) space and keeps the logic simple.
Is Last Visited Integers asked at Google/Amazon/Meta?
Problems with similar patterns appear in interviews at large tech companies because they test stream processing and state tracking. The concept of retrieving previous elements based on query history is a common simulation question involving arrays or stacks.
What data structure is used in Last Visited Integers?
The solution typically uses a dynamic array, stack, or deque to store visited integers. These structures allow constant-time insertion and efficient access to recently added elements, which is essential for retrieving the k-th last visited number.
What is the time complexity of Last Visited Integers?
The algorithm processes each operation exactly once, so the time complexity is O(n), where n is the number of operations in the input array. Each lookup for the k-th previous integer is O(1). The space complexity is O(n) to store previously visited integers.

Ready to solve this problem?

Practice Last Visited Integers with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays