LeetCode 2899 - Last Visited Integers

Difficulty: 🟢 Easy
Topics: Array, Simulation

Solution

Problem Understanding

The problem gives us an integer array nums that contains either positive integers or the value -1. We process the array from left to right while maintaining two conceptual arrays:

seen, which stores previously encountered positive integers
ans, which stores the answers for each -1

Whenever we encounter a positive integer, we insert it at the front of seen. This means the most recently seen positive integer is always at index 0.

Whenever we encounter -1, we look at how many consecutive -1 values have appeared up to the current position. Let this count be k.

If k <= len(seen), we append the k-th element of seen to the answer.
Otherwise, we append -1.

The important detail is that the count of consecutive -1s resets whenever we encounter a positive integer.

For example, suppose:

nums = [1, 2, -1, -1]

After processing 1 and 2, the seen array becomes:

[2, 1]

The first -1 asks for the 1st most recent integer, which is 2.

The second consecutive -1 asks for the 2nd most recent integer, which is 1.

So the output becomes:

[2, 1]

The constraints are very small:

1 <= nums.length <= 100
Values are either -1 or positive integers from 1 to 100

Because the input size is tiny, even less efficient approaches would work comfortably. However, the problem is fundamentally a simulation problem, and we can solve it cleanly in linear time.

Several edge cases are important:

The array may begin with -1, meaning no positive integers have been seen yet.
There may be more consecutive -1s than the number of stored values in seen.
Consecutive -1 counts must reset correctly after a positive integer appears.
The array may contain only positive integers, producing an empty answer array.

Approaches

Brute Force Approach

A brute force solution directly follows the problem statement very literally.

We maintain a list of all previously seen positive integers in insertion order. Whenever we encounter -1, we compute the consecutive count k, then rebuild or reverse the list to determine the k-th most recent value.

For example, if we stored positive integers as:

[1, 2, 3]

then the most recent values would conceptually be:

[3, 2, 1]

Each -1 query could require traversing backward through the array to find the requested element.

This approach is correct because it explicitly simulates the definition of the problem. However, repeated backward scans make it less efficient than necessary.

Optimal Approach

The key observation is that the problem always asks for recently seen integers in reverse chronological order.

Instead of storing numbers in normal order and repeatedly traversing backward, we can store the newest number at the front of the list.

Then:

seen[0] is the most recent integer
seen[1] is the second most recent
seen[2] is the third most recent

We also maintain a counter for consecutive -1s.

When we encounter:

A positive integer:
Insert it at the front of seen
Reset the consecutive -1 counter
A -1:
Increment the counter
Use the counter directly as an index lookup into seen

This gives a straightforward simulation with efficient lookups.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Repeated backward traversal for each `-1`
Optimal	O(n)	O(n)	Direct simulation using a recent-values list

Algorithm Walkthrough

Initialize an empty list called seen.

This list stores previously encountered positive integers in reverse chronological order. The newest value is always at the front. 2. Initialize an empty list called answer.

This list will store the result for each -1 encountered. 3. Initialize a variable consecutive_negatives = 0.

This tracks how many consecutive -1 values have appeared so far. 4. Iterate through each number in nums.

We process the array exactly once from left to right. 5. If the current number is positive:

Insert it at the front of seen.

Reset consecutive_negatives to 0 because the streak of consecutive -1s has been interrupted. 6. If the current number is -1:

Increment consecutive_negatives.

This value now represents k, the number of consecutive -1s. 7. Determine whether the requested index exists.

Since seen is zero-indexed:

The 1st most recent element is seen[0]
The 2nd most recent element is seen[1]
The k-th most recent element is seen[k - 1]

If k <= len(seen):

Append seen[k - 1] to answer.

Otherwise append -1. 9. After processing all elements, return answer.

Why it works

The algorithm maintains an invariant:

seen always stores previously encountered positive integers from most recent to least recent.
consecutive_negatives always equals the current streak length of consecutive -1s.

Because of this invariant, whenever we encounter a -1, the requested value is exactly the k-th element in seen, where k is the current consecutive count. If that position does not exist, the correct answer is -1.

Python Solution

from typing import List

class Solution:
    def lastVisitedIntegers(self, nums: List[int]) -> List[int]:
        seen = []
        answer = []
        consecutive_negatives = 0

        for num in nums:
            if num != -1:
                seen.insert(0, num)
                consecutive_negatives = 0
            else:
                consecutive_negatives += 1

                if consecutive_negatives <= len(seen):
                    answer.append(seen[consecutive_negatives - 1])
                else:
                    answer.append(-1)

        return answer

The implementation directly follows the simulation described earlier.

The seen list stores integers in reverse chronological order. We use insert(0, num) so that the newest value is always at the front.

The variable consecutive_negatives tracks how many -1s have appeared consecutively. Whenever a positive integer appears, the counter resets because the sequence of consecutive -1s is broken.

For every -1, we check whether the requested position exists inside seen. If it does, we append the corresponding value. Otherwise, we append -1.

Because the constraints are very small, using insert(0, num) is perfectly acceptable even though it shifts elements internally.

Go Solution

func lastVisitedIntegers(nums []int) []int {
    seen := []int{}
    answer := []int{}
    consecutiveNegatives := 0

    for _, num := range nums {
        if num != -1 {
            seen = append([]int{num}, seen...)
            consecutiveNegatives = 0
        } else {
            consecutiveNegatives++

            if consecutiveNegatives <= len(seen) {
                answer = append(answer, seen[consecutiveNegatives-1])
            } else {
                answer = append(answer, -1)
            }
        }
    }

    return answer
}

The Go implementation mirrors the Python logic closely.

Go slices do not have a built-in front insertion method like Python lists, so we create a new slice using:

append([]int{num}, seen...)

This prepends the new value to the front of the slice.

There are no integer overflow concerns because all values are very small. Empty slices are handled naturally in Go, so no special nil checks are required.

Worked Examples

Example 1

nums = [1, 2, -1, -1, -1]

Step	Current Value	seen	consecutive_negatives	answer
1	1	[1]	0	[]
2	2	[2, 1]	0	[]
3	-1	[2, 1]	1	[2]
4	-1	[2, 1]	2	[2, 1]
5	-1	[2, 1]	3	[2, 1, -1]

Final result:

[2, 1, -1]

Example 2

nums = [1, -1, 2, -1, -1]

Step	Current Value	seen	consecutive_negatives	answer
1	1	[1]	0	[]
2	-1	[1]	1	[1]
3	2	[2, 1]	0	[]
4	-1	[2, 1]	1	[1, 2]
5	-1	[2, 1]	2	[1, 2, 1]

Final result:

[1, 2, 1]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is processed once
Space	O(n)	The `seen` and `answer` arrays can both grow to size `n`

Although front insertion in Python lists and Go slices technically costs linear time per insertion, the constraints are extremely small, with n <= 100. In practice, the solution behaves efficiently and is considered linear for this problem size and intended solution style.

Test Cases

from typing import List

class Solution:
    def lastVisitedIntegers(self, nums: List[int]) -> List[int]:
        seen = []
        answer = []
        consecutive_negatives = 0

        for num in nums:
            if num != -1:
                seen.insert(0, num)
                consecutive_negatives = 0
            else:
                consecutive_negatives += 1

                if consecutive_negatives <= len(seen):
                    answer.append(seen[consecutive_negatives - 1])
                else:
                    answer.append(-1)

        return answer

solution = Solution()

assert solution.lastVisitedIntegers([1, 2, -1, -1, -1]) == [2, 1, -1]  # provided example 1
assert solution.lastVisitedIntegers([1, -1, 2, -1, -1]) == [1, 2, 1]  # provided example 2

assert solution.lastVisitedIntegers([-1]) == [-1]  # starts with -1
assert solution.lastVisitedIntegers([5]) == []  # no -1 values
assert solution.lastVisitedIntegers([7, -1]) == [7]  # single retrieval
assert solution.lastVisitedIntegers([1, 2, 3, -1, -1, -1]) == [3, 2, 1]  # retrieve all seen values
assert solution.lastVisitedIntegers([1, 2, -1, -1, -1, -1]) == [2, 1, -1, -1]  # exceed seen size
assert solution.lastVisitedIntegers([4, -1, 5, -1]) == [4, 5]  # reset consecutive count
assert solution.lastVisitedIntegers([10, -1, -1, 20, -1]) == [10, -1, 20]  # mixed resets and overflow
assert solution.lastVisitedIntegers([1, 2, 3]) == []  # only positive integers

Test	Why
`[1, 2, -1, -1, -1]`	Validates consecutive retrieval behavior
`[1, -1, 2, -1, -1]`	Validates reset of consecutive count
`[-1]`	Tests empty `seen` handling
`[5]`	Tests no output case
`[7, -1]`	Tests simplest successful lookup
`[1, 2, 3, -1, -1, -1]`	Tests retrieval of all stored values
`[1, 2, -1, -1, -1, -1]`	Tests requests beyond available history
`[4, -1, 5, -1]`	Tests interruption of consecutive `-1`s
`[10, -1, -1, 20, -1]`	Tests reset after invalid retrieval
`[1, 2, 3]`	Tests arrays with no `-1`

Edge Cases

Starting with `-1`

An input like:

[-1]

is important because no positive integers have been seen yet. A buggy implementation might attempt to access an element from an empty list.

The implementation handles this safely by checking:

if consecutive_negatives <= len(seen)

Since seen is empty, the condition fails and -1 is appended correctly.

More Consecutive `-1`s Than Available Values

Consider:

[1, 2, -1, -1, -1]

There are only two stored integers, but the third consecutive -1 requests the third most recent value.

Without proper bounds checking, this could produce an index error. The implementation avoids this by verifying the requested index exists before accessing the list.

Resetting Consecutive Counts Correctly