Last Visited Integers - Practice Coding Problems

Last Visited Integers - Problem

Array Simulation Easy

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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2,-1,-1,-1]

› Output: [2,1,-1]

💡 Note: After seeing 1,2: seen=[2,1]. First -1 (k=1): seen[0]=2. Second -1 (k=2): seen[1]=1. Third -1 (k=3): k > len(seen), so -1.

Example 2 — Reset Counter

$ Input: nums = [1,-1,2,-1,-1]

› Output: [1,2,1]

💡 Note: After 1: seen=[1]. First -1: seen[0]=1. After 2: seen=[2,1], counter resets. Next -1 (k=1): seen[0]=2. Last -1 (k=2): seen[1]=1.

Example 3 — No Positives

$ Input: nums = [-1,-1,-1]

› Output: [-1,-1,-1]

💡 Note: No positive numbers seen, so seen=[] is always empty. Every -1 results in -1 since k > len(seen).

Constraints

1 ≤ nums.length ≤ 1000
nums[i] == -1 or 1 ≤ nums[i] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input Processing

Array with positive numbers and -1s

Track Seen

Maintain list of recent positive numbers

Handle Queries

For each -1, find k-th most recent number

Key Takeaway

🎯 Key Insight: Use consecutive -1 count as index into most recently seen positive numbers

Asked in

G Google 15 M Microsoft 12 A Amazon 8

The key insight is to maintain a list of recently seen positive numbers and use the consecutive count of -1s as an index. The optimal approach uses a deque for O(1) prepend operations. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Simulation with Array	O(n²)	O(n)	Directly simulate the problem using arrays to track seen numbers and consecutive -1 count
Optimized with Deque/List	O(n)	O(n)	Use deque for O(1) prepend operations to optimize the simulation

Simulation with Array — Algorithm Steps

Iterate through nums array
For positive numbers: prepend to seen array
For -1: count consecutive -1s and get k-th element from seen
Add result to answer array

Visualization

Tap to expand

Step-by-Step Walkthrough

Process Positives

Prepend positive numbers to front of seen array

Count -1s

Track consecutive -1 count as index k

Lookup

Get k-th element from seen or -1 if out of bounds

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int* nums, int numsSize, int* returnSize) {
    int* seen = (int*)malloc(numsSize * sizeof(int));
    int* ans = (int*)malloc(numsSize * sizeof(int));
    int seenSize = 0;
    int ansSize = 0;
    int consecutiveMinusOnes = 0;
    
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] > 0) {
            // Positive number: prepend to front of seen
            for (int j = seenSize; j > 0; j--) {
                seen[j] = seen[j-1];
            }
            seen[0] = nums[i];
            seenSize++;
            consecutiveMinusOnes = 0; // Reset counter
        } else { // nums[i] == -1
            consecutiveMinusOnes++;
            // k is the number of consecutive -1s so far
            int k = consecutiveMinusOnes;
            
            if (k <= seenSize) {
                // Get k-th element (1-indexed, so k-1 for 0-indexed)
                ans[ansSize++] = seen[k-1];
            } else {
                ans[ansSize++] = -1;
            }
        }
    }
    
    free(seen);
    *returnSize = ansSize;
    return ans;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for array format [1,2,3]
    int nums[100];
    int numsSize = 0;
    char* ptr = strchr(line, '[');
    if (ptr) {
        ptr++;
        char* token = strtok(ptr, ",]");
        while (token) {
            nums[numsSize++] = atoi(token);
            token = strtok(NULL, ",]");
        }
    }
    
    int returnSize;
    int* result = solution(nums, numsSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n elements, prepending to array takes O(n) time in worst case

⚠ Quadratic Growth

Space Complexity

O(n)

Extra space for seen array to store positive numbers

⚡ Linearithmic Space

8.5K Views

Medium Frequency

~15 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Simulation with Array — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler