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 directly simulate according to the problem description.

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

We traverse the array \(\textit{nums}\):

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

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

Python3JavaC++GoTypeScriptRust

class Solution:
    def lastVisitedIntegers(self, nums: List[int]) -> List[int]:
        seen = []
        ans = []
        k = 0
        for x in nums:
            if x == -1:
                k += 1
                ans.append(-1 if k > len(seen) else seen[-k])
            else:
                k = 0
                seen.append(x)
        return ans

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

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

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
}

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

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

2899. Last Visited Integers

Description

Solutions

Solution 1: Simulation

Comments