How do you solve Last Visited Integers on LeetCode?

Last Visited Integers (LeetCode #2899) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Using a stack-like structure allows for efficient last-in-first-out access.

What is the brute force solution for Last Visited Integers?

The brute force approach for Last Visited Integers is Brute Force, with O(n²) time complexity and O(1) space complexity. In this approach, we will iterate through the array and for each -1, we will check the seen array to find the last visited integer. This is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Last Visited Integers?

Last Visited Integers uses the following concepts: Array, Simulation. The recommended patterns to study are: Stack, Array.

What are the interview tips for Last Visited Integers?

Explain your thought process clearly as you code. Consider edge cases early in your solution. Practice writing clean and efficient code.

What are common mistakes when solving Last Visited Integers?

Not handling the case where seen is empty correctly. Confusing the index of seen with the count of -1s.

#2899

Last Visited Integers

Easy

ArraySimulationStackArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

This approach efficiently uses a single pass through the array while maintaining a stack-like structure for the seen integers, allowing us to quickly access the last visited integer for each -1.

⚙️

Algorithm

4 steps

1Step 1: Initialize an empty list seen and a list ans.
2Step 2: Iterate through each element in nums.
3Step 3: If the element is a positive integer, prepend it to seen.
4Step 4: If the element is -1, check the length of seen. If it's greater than 0, append the last element of seen to ans; otherwise, append -1.

solution.py9 lines

1def lastVisitedIntegers(nums):
2    seen = []
3    ans = []
4    for num in nums:
5        if num != -1:
6            seen.insert(0, num)
7        else:
8            ans.append(seen[0] if seen else -1)
9    return ans

ℹ

Complexity note: The time complexity is O(n) because we only pass through the array once. The space complexity is O(n) due to the storage of seen integers.

1Using a stack-like structure allows for efficient last-in-first-out access.
2Handling edge cases (like consecutive -1s) is crucial for correctness.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.