# Last Visited Integers
**Difficulty:** EASY
[External](https://leetcode.com/problems/last-visited-integers)
Canonical: https://scaleengineer.com/dsa/problems/last-visited-integers
**Data structures:** Array
**Companies:** [General Motors](https://scaleengineer.com/companies/general-motors)
---
## Problem
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** `-1`s 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`

# Approaches
## Brute Force Simulation with List Prepending
This approach directly simulates the process described in the problem. It uses a list (like `ArrayList` in Java) to store the `seen` numbers. For each positive number, it's prepended to the `seen` list. When a `-1` is encountered, the `k`-th element is retrieved from the `seen` list. The main drawback is that prepending an element to an `ArrayList` is an inefficient operation.
**Time:** O(N*P), where N is the length of `nums` and P is the maximum number of positive integers seen so far. In the worst case, where most numbers are positive, P can be close to N, leading to a time complexity of O(N^2). The `add(0, element)` operation on an `ArrayList` takes time proportional to the list's size. · **Space:** O(N), for storing the `seen` and `ans` lists. In the worst case, `seen` can store up to N elements and `ans` can store up to N elements.
**Pros:** Simple to implement as it directly follows the problem description.; Easy to understand and reason about.
**Cons:** Inefficient due to the use of `list.add(0, element)`, which has a linear time complexity.; Performs poorly for large inputs (though constraints are small here).
### Explanation
We'll maintain a list `seen` to keep track of the positive integers encountered, and a list `ans` for the results. We also need a counter `k` for consecutive `-1`s.\n\nWe iterate through the input list `nums`.\n- If the current number `num` is positive, we add it to the beginning of the `seen` list using `seen.add(0, num)`. This operation requires shifting all existing elements, making it slow. We also reset the consecutive `-1` counter `k` to 0.\n- If the current number is `-1`, we increment `k`. We then check if `k` is within the bounds of the `seen` list's size. If `k <= seen.size()`, we retrieve the `(k-1)`-th element (since `k` is 1-based) and add it to `ans`. Otherwise, we add `-1` to `ans`.\n\nThis method is simple to understand as it follows the problem statement literally, but its performance suffers due to the repeated prepending operations.\n\n```java\nimport java.util.ArrayList;\nimport java.util.List;\n\nclass Solution {\n    public List<Integer> lastVisitedIntegers(List<Integer> nums) {\n        List<Integer> seen = new ArrayList<>();\n        List<Integer> ans = new ArrayList<>();\n        int k = 0;\n\n        for (int num : nums) {\n            if (num > 0) {\n                seen.add(0, num);\n                k = 0;\n            } else { // num == -1\n                k++;\n                if (k <= seen.size()) {\n                    ans.add(seen.get(k - 1));\n                } else {\n                    ans.add(-1);\n                }\n            }\n        }\n        return ans;\n    }\n}\n```
### Algorithm
- Initialize an empty list `seen` to store positive numbers.\n- Initialize an empty list `ans` to store the results.\n- Initialize a counter `k = 0` for consecutive `-1`s.\n- Iterate through each `num` in the input `nums`:\n  - If `num` is positive:\n    - Prepend `num` to `seen`.\n    - Reset `k` to `0`.\n  - If `num` is `-1`:\n    - Increment `k`.\n    - If `k` is less than or equal to the size of `seen`, append `seen.get(k-1)` to `ans`.\n    - Otherwise, append `-1` to `ans`.\n- Return the `ans` list.

## Optimized Simulation with List Appending
This approach improves upon the brute-force simulation by changing how the `seen` list is managed. Instead of prepending new numbers, which is slow, we append them to the end of the list. This makes adding new numbers a fast (amortized constant time) operation. To find the `k`-th last visited integer, we simply access the `k`-th element from the end of the list.
**Time:** O(N), where N is the length of `nums`. We iterate through the array once. Appending to an `ArrayList` (`add`) and accessing an element by index (`get`) are both amortized O(1) operations. · **Space:** O(N), for storing the `seen` and `ans` lists. In the worst case, `seen` can store up to N elements and `ans` can store up to N elements.
**Pros:** Efficient, with a linear time complexity.; Still relatively simple to implement and understand.
**Cons:** Requires slightly more thought than the direct simulation, as one needs to map the 'k-th last visited' concept to the correct index from the end of the list.
### Explanation
The core idea is to avoid the costly prepending operation. We still use an `ArrayList` for `seen`, but we'll add elements to the end. This means the `seen` list will store the positive numbers in the order they were encountered.\n\nThe algorithm is as follows:\n- Iterate through `nums`.\n- If `num` is positive, append it to `seen` using `seen.add(num)` and reset the consecutive `-1` counter `k`.\n- If `num` is `-1`, increment `k`. The `k`-th last visited integer is now the `k`-th element from the end of our `seen` list. If the size of `seen` is `s`, this element is at index `s - k`. We check if `k <= s`. If so, we get `seen.get(s - k)` and add it to `ans`. Otherwise, we add `-1`.\n\nBy using appending (`add`) and calculating the index from the end, all operations inside the loop become amortized O(1), leading to a much more efficient overall solution.\n\n```java\nimport java.util.ArrayList;\nimport java.util.List;\n\nclass Solution {\n    public List<Integer> lastVisitedIntegers(List<Integer> nums) {\n        List<Integer> seen = new ArrayList<>();\n        List<Integer> ans = new ArrayList<>();\n        int k = 0;\n\n        for (int num : nums) {\n            if (num > 0) {\n                seen.add(num);\n                k = 0;\n            } else { // num == -1\n                k++;\n                if (k <= seen.size()) {\n                    ans.add(seen.get(seen.size() - k));\n                } else {\n                    ans.add(-1);\n                }\n            }\n        }\n        return ans;\n    }\n}\n```
### Algorithm
- Initialize an empty list `seen` to store positive numbers.\n- Initialize an empty list `ans` to store the results.\n- Initialize a counter `k = 0` for consecutive `-1`s.\n- Iterate through each `num` in the input `nums`:\n  - If `num` is positive:\n    - Append `num` to `seen`.\n    - Reset `k` to `0`.\n  - If `num` is `-1`:\n    - Increment `k`.\n    - Let `s` be the size of `seen`.\n    - If `k` is less than or equal to `s`, append `seen.get(s - k)` to `ans`.\n    - Otherwise, append `-1` to `ans`.\n- Return the `ans` list.

# Solutions
### Java

```java
class Solution {
public
  List<Integer> lastVisitedIntegers(List<String> words) {
    List<Integer> nums = new ArrayList<>();
    List<Integer> ans = new ArrayList<>();
    int k = 0;
    for (var w : words) {
      if ("prev".equals(w)) {
        ++k;
        int i = nums.size() - k;
        ans.add(i < 0 ? -1 : nums.get(i));
      } else {
        k = 0;
        nums.add(Integer.valueOf(w));
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> lastVisitedIntegers(vector<string> &words) {
    vector<int> nums;
    vector<int> ans;
    int k = 0;
    for (auto &w : words) {
      if (w == "prev") {
        ++k;
        int i = nums.size() - k;
        ans.push_back(i < 0 ? -1 : nums[i]);
      } else {
        k = 0;
        nums.push_back(stoi(w));
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def lastVisitedIntegers(self, words: List[str]) -> List[int]: nums = [] ans = [] k = 0 for w in words: if w == "prev": k += 1 i = len(nums) - k ans . append(- 1 if i < 0 else nums[i]) else: k = 0 nums . append(int(w)) return ans

```