#2899

Easy

LeetCode Problem Workspace

Last Visited Integers

This problem involves finding the last visited integer for each -1 in a given array by simulating a stack-like behavior.

array simulation

Problem Statement

You are given an integer array nums where each element is either a positive integer or -1. For each occurrence of -1, find the most recently encountered positive integer in the array. This positive integer is called the 'last visited integer'.

To solve this, initialize two arrays, seen and ans. Start iterating from the beginning of nums. Push positive integers into the seen array, and for each -1, pop the most recent integer from seen and add it to the ans array.

Examples

Example 1

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

Output: [2,1,-1]

Start with seen = [] and ans = [] .

Example 2

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

Output: [1,2,1]

Start with seen = [] and ans = [] .

Constraints

1 <= nums.length <= 100
nums[i] == -1 or 1 <= nums[i] <= 100

Solution Approach

Iterate through the array

Start by iterating through the array. For each positive integer, add it to the seen array. For each -1, pop the most recent integer from seen and add it to the ans array. This simulates the stack behavior.

Space Complexity Consideration

The space complexity is determined by the seen array. In the worst case, if all elements in nums are positive integers, seen will store all of them. Therefore, the space complexity is O(n).

Time Complexity Consideration

The time complexity of the solution is O(n), where n is the length of the input array. This is because we iterate through the array once and perform constant time operations for each element.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n) since we iterate over the array once. The space complexity is O(n) because we store the positive integers in the seen array while processing the input.

What Interviewers Usually Probe

Ensure the candidate can correctly simulate stack behavior by popping from a list.
Look for understanding of stack simulation in an array context.
Observe if the candidate can properly handle the time and space complexities in array manipulation problems.

Common Pitfalls or Variants

Common pitfalls

Forgetting to handle the case where no positive integers have been encountered before a -1.
Improperly managing the state of the seen array between iterations.
Using unnecessary auxiliary arrays or overcomplicating the solution.

Follow-up variants

Consider handling edge cases with all positive integers or all -1s.
Try solving the problem with additional constraints on the array size or values.
Consider if a recursive solution could replace the iterative stack simulation.

FAQ

What is the time complexity of this problem?

The time complexity of this problem is O(n), where n is the length of the input array. We iterate through the array once.

How do I handle a -1 without a previous positive integer?

If -1 occurs without a preceding positive integer, the problem would typically assume the behavior as if there’s no valid positive integer to assign, depending on the problem's constraints.

What is the purpose of the `seen` array?

The seen array stores all encountered positive integers, acting as a stack from which we can pop values when a -1 is encountered.

Is there a way to optimize space usage?

Space optimization can be achieved by using a stack instead of an array, but in this case, the solution with an array is efficient enough given the problem constraints.

What does 'last visited integer' mean in the context of this problem?

The 'last visited integer' is the most recent positive integer encountered before a -1 in the array. It's analogous to the most recent value in a stack.

terminal

Solution

Solution 1: Simulation

We directly simulate according to the problem description.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def lastVisitedIntegers(self, nums: List[int]) -> List[int]:
        seen = []
        ans = []
        k = 0
        for x in nums:
            if x == -1:
                k += 1
                ans.append(-1 if k > len(seen) else seen[-k])
            else:
                k = 0
                seen.append(x)
        return ans

Continue Practicing