We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Last Visited Integers

Difficulty: Easy

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

Key Insights

  • We need to track the last positive integers encountered in the array.
  • Use a list seen to store the last visited integers in a way that allows easy access to the most recent ones.
  • Count consecutive -1s to determine which integer to append to the result array ans.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

The solution utilizes an array seen to keep track of the last visited positive integers in reverse order. As we iterate through the nums array, we check if the current number is positive or -1. If it's positive, we prepend it to seen. If it's -1, we determine how many consecutive -1s have been seen. We either append the corresponding element from seen to ans or -1 if there are not enough elements in seen.

Code Solutions

def lastVisitedIntegers(nums):
    seen = []
    ans = []
    count_negative = 0  # To count consecutive -1s

    for num in nums:
        if num != -1:
            seen.insert(0, num)  # Prepend the positive integer
        else:
            count_negative += 1  # Increment count of -1
            if count_negative <= len(seen):
                ans.append(seen[count_negative - 1])  # Append the k-th element
            else:
                ans.append(-1)  # Not enough elements in seen

    return ans
← Back to All Questions