Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Last Visited Integers solution and explanation

EasyArraySimulation8 min read62.2% acceptanceUpdated 9 Apr 2026
Practise Last Visited Integers
6:27
Leetcode BiWeekly contest 115 - Easy - Last Visited IntegersPrakhar Agrawal · 6:27 · 1K viewsWatch on YouTube
7 more videos on this problem
  1. Leetcode BiWeekly contest 115 - Easy - Last Visited IntegersPrakhar Agrawal · 6:27 · 1K views
  2. Leetcode Biweekly Contest 115 | 100095. Last Visited Integers | PythonBayu Aji · 1:36 · 550 views
  3. 100095. Last Visited Integers | Leetcode | Biweekly Contest 115.Optimization · 0:23 · 475 views
  4. 2899. Last Visited IntegersRounaq Khandelwal · 4:57 · 315 views
  5. 2899. Last Visited Integers (Leetcode Easy)Programming Live with Larry · 6:08 · 284 views
  6. Biweekly Contest 115 || 2899. Last Visited Integers || Easy ExplanationManas Kumar Panda · 13:43 · 113 views
  7. 2899. Last Visited Integers #leetcode #arraylist #googleinterview #amazoninterviewpreparationCodeVia · 3:38 · 85 views
  8. 100095. Last Visited Integers : Biweekly Contest 115 | Copy from description.BitByBit - Learn Coding · 0:18 · 32 views

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

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

Approach overview

Problem Overview: You receive a list of strings representing operations. A value can either be an integer or the string "prev". Every integer is recorded as a visited number. When you encounter "prev", return the k-th most recently visited integer where k equals how many consecutive "prev" operations have occurred since the last integer. If fewer than k integers exist, return -1. The task is essentially a stream simulation problem.

Approach 1: Using Two Stacks (O(n) time, O(n) space)

This approach explicitly models the operation history using two stacks. The first stack stores all integers seen so far. The second stack tracks results produced by consecutive "prev" calls. When a number appears, push it to the integer stack and clear the prev stack because the sequence of "prev" queries resets. When a "prev" operation appears, compute which previous element should be returned by referencing the integer stack index len(stack) - k. Push the returned value into the prev stack so the next "prev" automatically refers to the next older element. This method closely mirrors how the problem statement describes the behavior and is easy to reason about during interviews. Since each element is processed once, the total time complexity is O(n) with O(n) space to store visited integers. This technique fits naturally with problems involving history traversal and stack-like access patterns.

Approach 2: Using a Deque for Seen (O(n) time, O(n) space)

A cleaner simulation keeps all visited integers in a deque (or list) and tracks the current k value representing how many consecutive "prev" operations occurred. When an integer appears, append it to the deque and reset k = 0. When "prev" appears, increment k and check if the deque has at least k elements. If it does, return the element at index size - k; otherwise return -1. This approach avoids maintaining a second stack and relies on simple index lookup. The operations are constant time, so the full scan of the input array still runs in O(n) time with O(n) memory for the stored integers. It is a straightforward example of Array and Simulation working together with deque-style access patterns similar to a Stack.

Recommended for interviews: The deque/list simulation is typically the expected answer. It uses minimal state (a container plus a counter) and directly models the k-th previous lookup in constant time. Showing the stack-based reasoning first demonstrates understanding of the history behavior, while the optimized simulation highlights clean implementation skills.

Approach 1: Approach 1: Using Two Stacks

In this approach, we utilize two data structures: a stack to maintain the current viewed positive integers and another to handle queries simulated by -1. While iterating through the array, maintain the stack for positive integers. For each -1 encountered, manage a counter to handle consecutive -1s and respond accordingly by peeking into the positive stack.

def last_visited_integers_stack(nums):
    seen = []
    ans = []
    consecutive_neg1 = 0
    for num in nums:
        if num != -1:
            seen.append(num)
            consecutive_neg1 = 0
        else:
            consecutive_neg1 += 1
            if consecutive_neg1 <= len(seen):
                ans.append(seen[-consecutive_neg1])
            else:
                ans.append(-1)
    return ans

# Example usage
print(last_visited_integers_stack([1, 2, -1, -1, -1])) # Output: [2, 1, -1]
print(last_visited_integers_stack([1, -1, 2, -1, -1])) # Output: [1, 2, 1]
#include <stdio.h>

void lastVisitedIntegers(int nums[], int length, int result[]) {
    int seen[100], ans[100];
    int seenIndex = 0, ansIndex = 0, consecutiveNeg1 = 0;
    for(int i = 0; i < length; i++) {
        if(nums[i] != -1) {
            seen[seenIndex++] = nums[i];
            consecutiveNeg1 = 0;
        } else {
            consecutiveNeg1++;
            if(consecutiveNeg1 <= seenIndex) {
                ans[ansIndex++] = seen[seenIndex - consecutiveNeg1];
            } else {
                ans[ansIndex++] = -1;
            }
        }
    }
    for(int i = 0; i < ansIndex; i++)
        result[i] = ans[i];
}

int main() {
    int nums[] = {1, 2, -1, -1, -1};
    int result[5];
    lastVisitedIntegers(nums, 5, result);
    for(int i = 0; i < 3; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");
    return 0;
}

The function last_visited_integers_stack implements the logic of maintaining a stack (list) seen for positive integers in reverse order and a counter to track consecutive -1 occurrences. When a -1 is read, based on the historical positive numbers and the count of consecutive -1, it appends the correct element to the result list or -1 when not enough past positives exist.

Complexity

Time Complexity: O(n), where n is the length of the input list nums, as we traverse the list once.

Space Complexity: O(n), as we maintain potential elements for the seen stack and answer list.

Try this approach in the editor

Approach 2: Approach 2: Using a Deque for Seen

This approach optimizes the storage and retrieval of last visited elements using a double-ended queue (deque). This structure allows appending to the front and accessing elements by index efficiently. While iterating through the array, prepend new positive integers, and resolve -1 elements by determining their position against the sequence recorded in the deque.

import java.util.LinkedList;
import java.util.List;

public class LastVisitedIntegers {
    public static List<Integer> lastVisitedIntegersDeque(int[] nums) {
        LinkedList<Integer> seen = new LinkedList<>();
        List<Integer> ans = new LinkedList<>();
        int consecutiveNeg1 = 0;

        for (int num : nums) {
            if (num != -1) {
                seen.addFirst(num);
                consecutiveNeg1 = 0;
            } else {
                consecutiveNeg1++;
                if (consecutiveNeg1 <= seen.size()) {
                    ans.add(seen.get(consecutiveNeg1 - 1));
                } else {
                    ans.add(-1);
                }
            }
        }

        return ans;
    }

    public static void main(String[] args) {
        int[] nums1 = {1, 2, -1, -1, -1};
        System.out.println(lastVisitedIntegersDeque(nums1)); // Output: [2, 1, -1]

        int[] nums2 = {1, -1, 2, -1, -1};
        System.out.println(lastVisitedIntegersDeque(nums2)); // Output: [1, 2, 1]
    }
}
function lastVisitedIntegersDeque(nums) {
    const seen = [];
    const ans = [];
    let consecutiveNeg1 = 0;

    for (let num of nums) {
        if (num !== -1) {
            seen.unshift(num);
            consecutiveNeg1 = 0;
        } else {
            consecutiveNeg1++;
            if (consecutiveNeg1 <= seen.length) {
                ans.push(seen[consecutiveNeg1 - 1]);
            } else {
                ans.push(-1);
            }
        }
    }
    return ans;
}

console.log(lastVisitedIntegersDeque([1, 2, -1, -1, -1])); // Output: [2, 1, -1]
console.log(lastVisitedIntegersDeque([1, -1, 2, -1, -1])); // Output: [1, 2, 1]

The Java implementation utilizes LinkedList to implement a deque for managing past numbers efficiently, specifically leveraging addFirst for prepending and get for indexed access. The method iteratively resolves -1 queries by calculating their dependent position in sequence and collecting results into ans as a list.

Complexity

Time Complexity: O(n) where n is the size of the array; each action (prepend/access) is performed once per element.

Space Complexity: O(n) for storing visited positive numbers using LinkedList.

Try this approach in the editor

Approach 3: Simulation

We directly simulate according to the problem description.

Define an array seen to store the positive integers we have encountered, and an array ans to store the answer. We also need a variable k to record the number of consecutive -1s.

We traverse the array nums:

  • If the current element x = -1, we increment k by 1. If k is greater than the length of seen, we append -1 to ans; otherwise, we append the k-th element from the end of seen to ans.
  • If the current element x is a positive integer, we reset k to 0 and append x to the end of seen.

The time complexity is O(n) and the space complexity is O(n), where n is the length of the array nums.

class Solution {
public:
    vector<int> lastVisitedIntegers(vector<int>& nums) {
        vector<int> seen;
        vector<int> ans;
        int k = 0;

        for (int x : nums) {
            if (x == -1) {
                if (++k > seen.size()) {
                    ans.push_back(-1);
                } else {
                    ans.push_back(seen[seen.size() - k]);
                }
            } else {
                k = 0;
                seen.push_back(x);
            }
        }

        return ans;
    }
};
function lastVisitedIntegers(nums: number[]): number[] {
    const seen: number[] = [];
    const ans: number[] = [];
    let k = 0;

    for (const x of nums) {
        if (x === -1) {
            if (++k > seen.length) {
                ans.push(-1);
            } else {
                ans.push(seen.at(-k)!);
            }
        } else {
            k = 0;
            seen.push(x);
        }
    }

    return ans;
}
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, -1)
			} else {
				ans = append(ans, seen[len(seen)-k])
			}
		} else {
			k = 0
			seen = append(seen, x)
		}
	}

	return ans
}
impl Solution {
    pub fn last_visited_integers(nums: Vec<i32>) -> Vec<i32> {
        let mut seen: Vec<i32> = Vec::new();
        let mut ans: Vec<i32> = Vec::new();
        let mut k: i32 = 0;

        for x in nums {
            if x == -1 {
                k += 1;
                if k as usize > seen.len() {
                    ans.push(-1);
                } else {
                    ans.push(seen[seen.len() - k as usize]);
                }
            } else {
                k = 0;
                seen.push(x);
            }
        }

        ans
    }
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Approach 1: Using Two Stacks

Time Complexity: O(n), where n is the length of the input list nums, as we traverse the list once.

Space Complexity: O(n), as we maintain potential elements for the seen stack and answer list.

Approach 2: Using a Deque for Seen

Time Complexity: O(n) where n is the size of the array; each action (prepend/access) is performed once per element.

Space Complexity: O(n) for storing visited positive numbers using LinkedList.

Simulation–

Complexity analysis

ApproachTimeSpaceWhen to Use
Two StacksO(n)O(n)When you want an explicit representation of history traversal and consecutive prev queries.
Deque/List SimulationO(n)O(n)Best general solution. Minimal logic with constant-time lookup for the k-th last visited value.

Frequently asked questions

Is Last Visited Integers easy or hard?

Last Visited Integers is classified as an Easy problem on LeetCode with an acceptance rate above 60%. The main challenge is correctly tracking consecutive "prev" queries and mapping them to the k-th previously seen integer.

Last Visited Integers Python/Java solution

In Python, a list is usually used to store visited integers and access elements using negative indexing. In Java, an ArrayList or ArrayDeque works well for maintaining the sequence and retrieving elements using size-based indexing.

How to solve Last Visited Integers in O(n)?

Iterate through the operations array while storing every integer in a list. Maintain a counter k that increments for each "prev" query and resets when a new integer appears. For each "prev", return nums[len(nums) - k] if the index exists; otherwise return -1. This single pass guarantees O(n) time.

What is the best approach for Last Visited Integers?

The most practical approach stores all visited integers in a list or deque and tracks the number of consecutive "prev" queries using a counter k. Each "prev" returns the element at index size - k if it exists. This simulation runs in O(n) time and O(n) space and keeps the logic simple.

Is Last Visited Integers asked at Google/Amazon/Meta?

Problems with similar patterns appear in interviews at large tech companies because they test stream processing and state tracking. The concept of retrieving previous elements based on query history is a common simulation question involving arrays or stacks.

What data structure is used in Last Visited Integers?

The solution typically uses a dynamic array, stack, or deque to store visited integers. These structures allow constant-time insertion and efficient access to recently added elements, which is essential for retrieving the k-th last visited number.

What is the time complexity of Last Visited Integers?

The algorithm processes each operation exactly once, so the time complexity is O(n), where n is the number of operations in the input array. Each lookup for the k-th previous integer is O(1). The space complexity is O(n) to store previously visited integers.

Comments

Now write it yourselfClose this page and solve Last Visited Integers in the editor, without looking.
Practise Last Visited Integers