2899. Last Visited Integers
Problem Description
The problem provides us with an array of strings where each element is either a string that represents a positive integer or the string "prev". Weāre required to iterate through this array and, whenever we encounter the string "prev", we must find the last visited integer according to specific rules.
For a sequence of one or more "prev" strings, the number of consecutive "prev" strings (including the current "prev") is counted as k. We have to look at the integers seen so far in reverse order. The last visited integer is the (k-1)th integer in this reversed order. If k exceeds the total number of integers weāve seen, then the last visited integer is to be considered -1.
Our goal is to return an array of integers, which includes the last visited integer for each "prev" string found in the input array.
For example, given an input array of ["1", "2", "prev", "prev", "3", "prev"]
, our output should be [2, 1, -1]
.
Intuition
The intuition behind the solution is to simulate the process described, keeping track of two essential pieces of information: the integers we have seen (in order) and the current sequence length of "prev" strings (k).
To achieve this, we can keep an array called nums
to store all the integers we have encountered so far in the order they were visited. We also keep a count k
, which is reset to 0 every time we encounter an integer and is incremented when we encounter a "prev". Whenever we bump into a "prev", we look k elements back from the end of our stored integersāif there are enough elementsāand add that to the result array. If there are not enough elements (k is greater than the number of integers encountered), we add -1 to the result.
Essentially, we are creating a stack of numbers encountered, and for every "prev", we are performing a lookup that acts like indexing from the back of the stack by k positions, simulating the process of tracking the last visited integers.
Solution Approach
The solution follows a simple simulation approach that revolves around keeping track of the visited integers and the number of consecutive occurrences of "prev". This approach can be outlined as follows:
- We initialize an array
nums
to store integers that have been seen. This array acts as a stack where we can easily add new integers and look up past integers. - A variable
k
is used to keep count of consecutive "prev" strings. It is reset to 0 whenever a non-"prev" string (i.e., an integer) is encountered. - We iterate through the
words
array, processing one string at a time. - If the current word is not "prev" (it is a positive integer), we reset
k
to 0 and append the integer form of the word tonums
. - If the current word is "prev", we increment
k
by 1 to account for the new "prev" string in the sequence. - We then attempt to retrieve the last visited integer by looking
k
places from the end ofnums
using the indexlen(nums) - k
. Ifk
is within the range ofnums
, we append the desired integer toans
; otherwise, we append-1
, indicating that there are not enough visited integers to satisfy the "prev" condition. - After processing all words in the array, we return the
ans
array, which contains the last visited integer for each "prev" encountered.
The solution uses straightforward array manipulation and conditions to achieve the objective, employing basic data structures (lists in Python), and index manipulation. The primary pattern this solution leverages is iteration with condition checks, ensuring the last visited integer is correctly identified and handled according to the problem's rules.
Here's a breakdown of the code corresponding to the steps above:
1class Solution:
2 def lastVisitedIntegers(self, words: List[str]) -> List[int]:
3 nums = [] # Step 1: initialize the stack of seen integers
4 ans = [] # Initialize the array for storing last visited integers
5 k = 0 # Initialize the count of consecutive "prev"
6 for w in words: # Step 3: iterate through each word
7 if w == "prev": # Step 4 and 5: handle "prev"
8 k += 1 # Increment count for consecutive "prev"
9 i = len(nums) - k # Calculate index for the last visited integer
10 ans.append(-1 if i < 0 else nums[i]) # Append the last visited integer or -1
11 else: # Step 6: reset k and add new integer to nums
12 k = 0
13 nums.append(int(w)) # Convert string to integer and add to nums
14 return ans # Step 7: return the result
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's go through an example to illustrate the solution approach using a small input array: ["10", "prev", "20", "prev", "prev"]
.
-
Initialize
nums
as an empty array to represent the stack of seen integers,ans
as an empty array for the last visited integers, andk
as 0 for the count of consecutive "prev" strings. -
Iterate through each element in
words
:- For the first element
"10"
, since it is not "prev", resetk
to 0 (it's already 0). Convert"10"
to an integer and append it tonums
. Nownums = [10]
. - The second element is
"prev"
. Incrementk
to 1 (k was 0). Calculate the index:len(nums) - k
which is0
. There is an available integer, so appendnums[0]
(which is10
) toans
. Nowans = [10]
. - The third element
"20"
is not "prev", so resetk
to 0 and append20
tonums
. Nownums = [10, 20]
. - The fourth element is again
"prev"
. Incrementk
to 1. Calculate indexlen(nums) - k
which is1
. Appendnums[1]
(which is20
) toans
. Nowans = [10, 20]
. - The last element is
"prev"
again. Incrementk
to 2 (since we do not resetk
as the element is "prev"). Calculate indexlen(nums) - k
which is0
. Appendnums[0]
(which is10
) toans
. Nowans = [10, 20, 10]
.
- For the first element
-
Finally, we end up with
ans = [10, 20, 10]
, which is the output, with each entry representing the last visited integer for each "prev".
By processing each element one by one and keeping track of the seen integers (nums
) and the consecutive count of "prev" (k
), we can efficiently simulate the process and determine the last visited integer or -1
when required.
Solution Implementation
1class Solution:
2 def lastVisitedIntegers(self, words: List[str]) -> List[int]:
3 # Initialize a list to keep track of the integers seen so far.
4 seen_numbers = []
5 # Initialize a list to keep track of the outputs for each "prev" command.
6 output = []
7 # Counter to keep track of how many "prev" commands have been seen consecutively.
8 prev_count = 0
9 # Iterate through each word in the words list.
10 for word in words:
11 if word == "prev":
12 # Increment the 'prev' counter if the current word is "prev".
13 prev_count += 1
14 # Compute the index of the integer to access based on 'prev_count'.
15 index = len(seen_numbers) - prev_count
16 # Append the number to the output if it exists, otherwise append -1.
17 output.append(-1 if index < 0 else seen_numbers[index])
18 else:
19 # Reset 'prev_count' to 0 since the current word is a number.
20 prev_count = 0
21 # Convert the word to an integer and append it to the seen_numbers.
22 seen_numbers.append(int(word))
23 # Return the output list which contains the integers or -1 for each "prev".
24 return output
25
1import java.util.ArrayList;
2import java.util.List;
3
4class Solution {
5
6 // Method to find the last visited integers based on given words
7 public List<Integer> lastVisitedIntegers(List<String> words) {
8 // A list to store the actual numbers seen so far.
9 List<Integer> numbers = new ArrayList<>();
10
11 // A list to store the result of previously visited numbers.
12 List<Integer> result = new ArrayList<>();
13
14 // Variable to keep track of how many 'prev' operations have been encountered.
15 int prevCount = 0;
16
17 // Iterate over each word in the input list.
18 for (String word : words) {
19 if ("prev".equals(word)) {
20 // If the word is 'prev', increment the counter and get the last visited number.
21 prevCount++;
22 int index = numbers.size() - prevCount; // Calculate the index for previously visited number.
23 if (index < 0) {
24 // If the index is out of bounds, add -1 to the result.
25 result.add(-1);
26 } else {
27 // Otherwise, add the number at the calculated index to the result.
28 result.add(numbers.get(index));
29 }
30 } else {
31 // If the word is a number, reset the counter and add the number to our number list.
32 prevCount = 0;
33 numbers.add(Integer.valueOf(word));
34 }
35 }
36
37 // Return the result list containing the last visited numbers.
38 return result;
39 }
40}
41
1#include <vector>
2#include <string>
3using namespace std;
4
5class Solution {
6public:
7 // Function to process a list of strings and return a vector representing the last visited integers
8 vector<int> lastVisitedIntegers(vector<string>& words) {
9 vector<int> nums; // Vector to store parsed integers from the 'words' vector
10 vector<int> ans; // Vector to store answers for each "prev" command
11 int prevCounter = 0; // Counter to keep track of the "prev" commands
12
13 // Iterate over the words
14 for (auto& word : words) {
15 // If the current word is "prev", find the previously encountered integer
16 if (word == "prev") {
17 ++prevCounter; // Increment counter for each "prev"
18 int index = nums.size() - prevCounter; // Calculate the index for the previously visited integer
19
20 // If the index is valid, push the found integer to the 'ans' vector; otherwise push -1
21 ans.push_back(index < 0 ? -1 : nums[index]);
22 } else {
23 // Reset the prevCounter and add the numeric value of the word to the 'nums' vector
24 prevCounter = 0;
25 nums.push_back(stoi(word));
26 }
27 }
28
29 return ans; // Return the result vector
30 }
31};
32
1function lastVisitedIntegers(words: string[]): number[] {
2 // Initialize a list to keep track of numeric inputs
3 const numberList: number[] = [];
4 // Initialize a list for the answer which will hold the last visited integers
5 const answerList: number[] = [];
6 // Initialize a counter to keep track of the "prev" commands
7 let prevCounter = 0;
8
9 // Iterate through each word in the input array
10 for (const word of words) {
11 // Check if the current word is the 'prev' command
12 if (word === 'prev') {
13 // Increment the counter as we've encountered a 'prev'
14 ++prevCounter;
15 // Calculate the index we want to access
16 const indexToAccess = numberList.length - prevCounter;
17 // Check if the index is valid, if not, push -1 to answerList
18 answerList.push(indexToAccess < 0 ? -1 : numberList[indexToAccess]);
19 } else {
20 // Reset the counter since a number is encountered
21 prevCounter = 0;
22 // Convert the string to a number and push to the numberList
23 numberList.push(Number(word));
24 }
25 }
26
27 // Return the answer list containing all last visited integers on encountering 'prev'
28 return answerList;
29}
30
Time and Space Complexity
Time Complexity
The time complexity of the code is O(n)
, where n
is the length of the words
array. We iterate over each word in the array once. In the iteration, the operations we perform, such as checking the value of w
and updating the nums
list or the index k
, all have constant time complexity (O(1)
). Even when we access nums[i]
the time complexity is O(1)
because list indexing is a constant time operation in Python. Hence, the main contributing factor to the time complexity is the single loop through the words
array, resulting in O(n)
time complexity.
Space Complexity
The space complexity of the code is also O(n)
. We use additional data structure nums
to store the integers as they appear when they are not "prev". Thus, in the worst-case scenario where there is no "prev", nums
will have the same number of integers as there are elements in the words
list. The ans
list at most will contain n
"-1" integers when all elements in words
are "prev". The sum of the size of nums
and ans
lists dictates the space complexity. Therefore, the space complexity is O(n)
due to the storage requirements that scale linearly with the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following is a min heap?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time