Last Visited Integers

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 -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.

Examples

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

Solution

Method 1 – Simulation with Deque

Intuition

We simulate the process as described: maintain a deque for the seen numbers and count consecutive -1s to answer each query. This is a direct simulation problem.

Approach

1. Initialize an empty deque seen and an empty list ans.
2. Iterate through nums:
   • If the number is positive, prepend it to seen and reset the consecutive -1 counter.
   • If the number is -1, increment the counter, and if the counter is less than or equal to the length of seen, append the k-th element of seen to ans, else append -1.
3. Return ans.

Code

C++

class Solution {
public:
    vector<int> lastVisitedIntegers(vector<int>& nums) {
        deque<int> seen;
        vector<int> ans;
        int k = 0;
        for (int x : nums) {
            if (x == -1) {
                ++k;
                if (k <= seen.size()) ans.push_back(seen[k-1]);
                else ans.push_back(-1);
            } else {
                seen.push_front(x);
                k = 0;
            }
        }
        return ans;
    }
};

Go

func lastVisitedIntegers(nums []int) []int {
    seen := []int{}
    ans := []int{}
    k := 0
    for _, x := range nums {
        if x == -1 {
            k++
            if k <= len(seen) {
                ans = append(ans, seen[k-1])
            } else {
                ans = append(ans, -1)
            }
        } else {
            seen = append([]int{x}, seen...)
            k = 0
        }
    }
    return ans
}

Java

class Solution {
    public List<Integer> lastVisitedIntegers(int[] nums) {
        LinkedList<Integer> seen = new LinkedList<>();
        List<Integer> ans = new ArrayList<>();
        int k = 0;
        for (int x : nums) {
            if (x == -1) {
                k++;
                if (k <= seen.size()) ans.add(seen.get(k-1));
                else ans.add(-1);
            } else {
                seen.addFirst(x);
                k = 0;
            }
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun lastVisitedIntegers(nums: IntArray): List<Int> {
        val seen = ArrayDeque<Int>()
        val ans = mutableListOf<Int>()
        var k = 0
        for (x in nums) {
            if (x == -1) {
                k++
                if (k <= seen.size) ans.add(seen.elementAt(k-1))
                else ans.add(-1)
            } else {
                seen.addFirst(x)
                k = 0
            }
        }
        return ans
    }
}

Python

class Solution:
    def lastVisitedIntegers(self, nums: list[int]) -> list[int]:
        from collections import deque
        seen = deque()
        ans = []
        k = 0
        for x in nums:
            if x == -1:
                k += 1
                if k <= len(seen):
                    ans.append(seen[k-1])
                else:
                    ans.append(-1)
            else:
                seen.appendleft(x)
                k = 0
        return ans

Rust

impl Solution {
    pub fn last_visited_integers(nums: Vec<i32>) -> Vec<i32> {
        let mut seen = std::collections::VecDeque::new();
        let mut ans = vec![];
        let mut k = 0;
        for x in nums {
            if x == -1 {
                k += 1;
                if k <= seen.len() {
                    ans.push(seen[k-1]);
                } else {
                    ans.push(-1);
                }
            } else {
                seen.push_front(x);
                k = 0;
            }
        }
        ans
    }
}

TypeScript

class Solution {
    lastVisitedIntegers(nums: number[]): number[] {
        const seen: number[] = [];
        const ans: number[] = [];
        let k = 0;
        for (const x of nums) {
            if (x === -1) {
                k++;
                if (k <= seen.length) ans.push(seen[k-1]);
                else ans.push(-1);
            } else {
                seen.unshift(x);
                k = 0;
            }
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n^2) worst case (due to prepend in some languages), but O(n) average for most practical cases.
• 🧺 Space complexity: O(n), for storing seen and ans arrays.