2899. Last Visited Integers

Description

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 = [].

Process nums[0]: The first element in nums is 1. We prepend it to the front of seen. Now, seen == [1].
Process nums[1]: The next element is 2. We prepend it to the front of seen. Now, seen == [2, 1].
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].
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].
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 = [].

Process nums[0]: The first element in nums is 1. We prepend it to the front of seen. Now, seen == [1].
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].
Process nums[2]: The next element is 2. Prepend this to the front of seen. Now, seen == [2, 1].
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].
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

Solutions

Solution 1: Simulation

We can directly simulate according to the problem statement. In the implementation, we use an array \(nums\) to store the traversed integers, and an integer \(k\) to record the current number of consecutive \(prev\) strings. If the current string is \(prev\), we take out the \(|nums| - k-th\) integer from \(nums\). If it does not exist, we return \(-1\).

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

Python3JavaC++GoTypeScriptRust

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

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;
    }
}

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;
    }
};

func lastVisitedIntegers(words []string) (ans []int) {
    nums := []int{}
    k := 0
    for _, w := range words {
        if w == "prev" {
            k++
            i := len(nums) - k
            if i < 0 {
                ans = append(ans, -1)
            } else {
                ans = append(ans, nums[i])
            }
        } else {
            k = 0
            x, _ := strconv.Atoi(w)
            nums = append(nums, x)
        }
    }
    return
}

function lastVisitedIntegers(words: string[]): number[] {
    const nums: number[] = [];
    const ans: number[] = [];
    let k = 0;
    for (const w of words) {
        if (w === 'prev') {
            ++k;
            const i = nums.length - k;
            ans.push(i < 0 ? -1 : nums[i]);
        } else {
            k = 0;
            nums.push(+w);
        }
    }
    return ans;
}

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

        for w in words {
            if w == "prev" {
                k += 1;
                let i = (nums.len() as i32) - k;
                ans.push(if i < 0 { -1 } else { nums[i as usize] });
            } else {
                k = 0;
                nums.push(w.parse::<i32>().unwrap());
            }
        }

        ans
    }
}

2899. Last Visited Integers

Description

Solutions

Solution 1: Simulation

Comments