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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Last Visited Integers

Number: 3164

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given an array of integers where each element is either a positive integer or -1, the goal is to determine the "last visited integer" for each occurrence of -1. Process the array from left to right using an auxiliary array called seen, where every positive integer is prepended. For each -1 encountered, count the number of consecutive -1’s (including the current one) as k; if k is within the bounds of seen, append the k-th element from seen to the answer array, otherwise append -1.

Key Insights

  • Maintain a list (seen) that stores positive integers in reverse order of their appearance.
  • Use a counter to track the number of consecutive -1's.
  • Reset the consecutive -1 counter whenever a positive integer is encountered.
  • For each -1, use the counter to determine which element from seen to pick (if available) or output -1 if the counter exceeds the length of seen.

Space and Time Complexity

Time Complexity: O(n) since we process each element in the array once. Space Complexity: O(n) for storing the seen and answer arrays.

Solution

The solution involves a single pass over the input array. As you iterate:

  1. For a positive integer, prepend it to the seen list and reset the consecutive -1 counter.
  2. For each -1, increment the counter. If the counter is less than or equal to the length of seen, retrieve the element at position (counter - 1) from seen and append it to the answer; otherwise, append -1. This approach uses simple list operations and a counter to simulate the required behavior.

Code Solutions

# Function to compute last visited integers
def lastVisitedIntegers(nums):
    # List to keep track of seen positive integers (in reverse order)
    seen = []
    # List for the resulting last visited integers
    ans = []
    # Counter for consecutive occurrences of -1
    consecutive_minus_one = 0

    # Process each number in the input array
    for num in nums:
        if num != -1:
            # Prepend positive integer to seen list
            seen.insert(0, num)
            # Reset the consecutive -1 counter
            consecutive_minus_one = 0
        else:
            # Increment consecutive -1 counter
            consecutive_minus_one += 1
            # Check if k (consecutive count) is within the bounds of seen list
            if consecutive_minus_one <= len(seen):
                ans.append(seen[consecutive_minus_one - 1])
            else:
                # Not enough elements in seen, return -1
                ans.append(-1)
    return ans

# Example usage:
print(lastVisitedIntegers([1,2,-1,-1,-1]))
← Back to All Questions