Longest Uploaded Prefix - Practice Coding Problems

Longest Uploaded Prefix - Problem

Hash Table Binary Search Union Find Design Binary Indexed Tree Segment Tree Heap (Priority Queue) Ordered Set Medium

You are given a stream of n videos, each represented by a distinct number from 1 to n that you need to upload to a server. You need to implement a data structure that calculates the length of the longest uploaded prefix at various points in the upload process.

We consider i to be an uploaded prefix if all videos in the range 1 to i (inclusive) have been uploaded to the server. The longest uploaded prefix is the maximum value of i that satisfies this definition.

Implement the LUPrefix class:

LUPrefix(int n) Initializes the object for a stream of n videos.
void upload(int video) Uploads video to the server.
int longest() Returns the length of the longest uploaded prefix defined above.

Input & Output

Example 1 — Basic Operation Sequence

$ Input: operations = [["LUPrefix",4],["upload",3],["longest"],["upload",1],["longest"],["upload",2],["longest"]]

› Output: [null,null,0,null,1,null,3]

💡 Note: Initialize with n=4. Upload 3: longest prefix is 0 (video 1 missing). Upload 1: prefix is 1. Upload 2: now videos 1,2,3 are consecutive, so prefix is 3.

Example 2 — Sequential Uploads

$ Input: operations = [["LUPrefix",3],["upload",1],["longest"],["upload",2],["longest"],["upload",3],["longest"]]

› Output: [null,null,1,null,2,null,3]

💡 Note: Upload in order 1,2,3. Each upload extends the prefix: 1→1, 2→2, 3→3.

Example 3 — Reverse Order

$ Input: operations = [["LUPrefix",2],["upload",2],["longest"],["upload",1],["longest"]]

› Output: [null,null,0,null,2]

💡 Note: Upload 2 first: prefix is 0 (video 1 missing). Upload 1: now both 1,2 are uploaded, prefix becomes 2.

Constraints

1 ≤ n ≤ 10⁵
1 ≤ video ≤ n
All values of video are distinct
At most 2 × 10⁵ calls will be made to upload and longest

Visualization

Tap to expand

Understanding the Visualization

Input

Stream of video uploads (1 to n)

Process

Track consecutive uploads from video 1

Output

Length of longest consecutive prefix

Key Takeaway

🎯 Key Insight: Only count consecutive videos starting from 1 - maintain current prefix length and extend when gaps are filled

Asked in

G Google 25 a Amazon 20 f Meta 15

The key insight is to maintain the current prefix length and extend it efficiently when consecutive videos become available. The optimized approach uses a boolean array to track uploads and maintains the current prefix length, extending it in O(1) amortized time per upload. Time: O(n) total for all operations, Space: O(n) for the boolean array.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with Set Check	O(n)	O(n)	Store uploaded videos in a set and check from 1 to n for each longest() call
Boolean Array with Prefix Tracking	O(n)	O(n)	Use boolean array to track uploads and maintain current prefix length

Brute Force with Set Check — Algorithm Steps

Store uploaded videos in a hash set
For longest(), check videos 1, 2, 3... until finding a missing one
Return the count of consecutive videos found

Visualization

Tap to expand

Step-by-Step Walkthrough

Store Upload

Add uploaded video to set

Scan Sequence

Check videos 1, 2, 3... until gap found

Return Count

Return length of consecutive sequence

Code -

solution.c — C

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

typedef struct {
    int n;
    bool* uploaded;
} LUPrefix;

LUPrefix* createLUPrefix(int n) {
    LUPrefix* obj = (LUPrefix*)malloc(sizeof(LUPrefix));
    obj->n = n;
    obj->uploaded = (bool*)calloc(n + 1, sizeof(bool));
    return obj;
}

void upload(LUPrefix* obj, int video) {
    obj->uploaded[video] = true;
}

int longest(LUPrefix* obj) {
    for (int i = 1; i <= obj->n; i++) {
        if (!obj->uploaded[i]) {
            return i - 1;
        }
    }
    return obj->n;
}

void freeLUPrefix(LUPrefix* obj) {
    free(obj->uploaded);
    free(obj);
}

int main() {
    // This is a simplified version for the brute force approach
    // Full implementation would parse the operations array
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each longest() call iterates through up to n videos to find the prefix

✓ Linear Growth

Space Complexity

O(n)

Hash set stores up to n uploaded video IDs

⚡ Linearithmic Space

12.0K Views

Medium Frequency

~25 min Avg. Time

450 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

Brute Force with Set Check — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler