LeetCode 2424 - Longest Uploaded Prefix

LeetCode Problem 2424

Difficulty: 🟡 Medium
Topics: Hash Table, Binary Search, Union-Find, Design, Binary Indexed Tree, Segment Tree, Heap (Priority Queue), Ordered Set

Solution

Problem Understanding

The problem asks us to design a data structure that tracks uploaded videos and continuously reports the length of the longest uploaded prefix.

A prefix of uploaded videos means that every video from 1 through i has already been uploaded. The goal is to return the maximum such i.

For example, suppose the uploaded videos are:

[1, 2, 3]

Then the longest uploaded prefix is 3, because videos 1, 2, and 3 are all present.

If the uploaded videos are:

[2, 3, 4]

Then the longest uploaded prefix is 0, because video 1 is missing, so there is no valid prefix starting from 1.

The input stream consists of upload operations, where each uploaded video number is unique and lies in the range 1 to n.

The class must support three operations:

1. Initialization with n
2. Uploading a video
3. Querying the longest uploaded prefix

The constraints are important:

• n can be as large as 100000
• There can be up to 200000 total calls
• Video numbers are distinct

These limits tell us that inefficient scanning approaches could become too slow. We need operations that are close to constant time.

An important observation is that uploads arrive in arbitrary order. We cannot assume videos are uploaded sequentially.

For example:

upload(5)
upload(1)
upload(2)
upload(4)
upload(3)

The longest prefix changes like this:

0 -> 1 -> 2 -> 2 -> 5

The main challenge is efficiently tracking the first missing video in the sequence.

Important edge cases include:

• Uploading videos completely out of order
• Querying before video 1 is uploaded
• Uploading all videos
• Smallest possible input, where n = 1

The problem guarantees that uploads are distinct, so we do not need to handle duplicate uploads.

Approaches

Brute Force Approach

A straightforward solution is to maintain a set of uploaded videos. Whenever longest() is called, we start from 1 and scan upward until we find the first missing video.

For example:

Uploaded: {1, 2, 3, 5}

We check:

1 -> present
2 -> present
3 -> present
4 -> missing

So the answer is 3.

This approach is correct because the definition of the longest uploaded prefix directly requires checking consecutive presence from 1.

However, this becomes inefficient when many longest() calls are made. In the worst case, every query may scan up to n elements.

With up to 200000 operations, this can lead to time complexity close to O(n * q), which is too slow.

Optimal Approach

The key observation is that the longest uploaded prefix only moves forward, never backward.

Suppose the current longest prefix is:

current = 3

This means videos 1, 2, and 3 are uploaded.

When a new video is uploaded, the only thing we need to check is whether video 4 is now available. If it is, we can extend the prefix forward as far as possible.

This suggests maintaining:

• A boolean array or hash set to track uploaded videos
• A pointer representing the current longest prefix

Whenever a video is uploaded:

1. Mark it as uploaded
2. While the next video in sequence exists, advance the pointer

Each video is processed at most once during pointer advancement, making the total work linear across all operations.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n) per longest()	O(n)	Repeatedly scans from 1 upward
Optimal	O(1) amortized per operation	O(n)	Uses a moving pointer and upload tracking

Algorithm Walkthrough

Optimal Algorithm

1. Create a boolean array called uploaded of size n + 2.

We use this array to quickly determine whether a video has been uploaded. Index i corresponds to video i. 2. Maintain an integer pointer called longest_prefix.

This stores the largest prefix currently known to be fully uploaded. 3. Initially, set:

longest_prefix = 0

Since no videos are uploaded yet, the longest prefix length is zero. 4. When upload(video) is called:

• Mark the video as uploaded:

uploaded[video] = True

• Then repeatedly check whether the next required video exists:

while uploaded[longest_prefix + 1]:
    longest_prefix += 1

5. When longest() is called:

• Simply return longest_prefix

Why it works

The invariant is that all videos from 1 through longest_prefix are uploaded, and longest_prefix + 1 is not uploaded.

Whenever a new upload occurs, the only possible change is that the prefix may extend forward. Since the pointer only moves forward and each video advances the pointer at most once, the algorithm remains efficient while always maintaining the correct prefix length.

Python Solution

class LUPrefix:

    def __init__(self, n: int):
        self.uploaded = [False] * (n + 2)
        self.longest_prefix = 0

    def upload(self, video: int) -> None:
        self.uploaded[video] = True

        while self.uploaded[self.longest_prefix + 1]:
            self.longest_prefix += 1

    def longest(self) -> int:
        return self.longest_prefix

# Your LUPrefix object will be instantiated and called as such:
# obj = LUPrefix(n)
# obj.upload(video)
# param_2 = obj.longest()

The implementation uses a boolean array named uploaded to record whether each video has been uploaded.

The array size is n + 2 so that checking longest_prefix + 1 never causes an out-of-bounds error when all videos are uploaded.

The variable longest_prefix stores the current valid prefix length.

Inside upload, the uploaded video is marked as True. Then the while loop attempts to extend the prefix forward as long as the next required video exists.

The important efficiency detail is that longest_prefix never decreases. Every video contributes to pointer advancement at most once across the entire execution.

The longest() method becomes extremely efficient because it simply returns the already-maintained prefix length.

Go Solution

type LUPrefix struct {
	uploaded      []bool
	longestPrefix int
}

func Constructor(n int) LUPrefix {
	return LUPrefix{
		uploaded:      make([]bool, n+2),
		longestPrefix: 0,
	}
}

func (this *LUPrefix) Upload(video int) {
	this.uploaded[video] = true

	for this.uploaded[this.longestPrefix+1] {
		this.longestPrefix++
	}
}

func (this *LUPrefix) Longest() int {
	return this.longestPrefix
}

/**
 * Your LUPrefix object will be instantiated and called as such:
 * obj := Constructor(n);
 * obj.Upload(video);
 * param_2 := obj.Longest();
 */

The Go implementation closely mirrors the Python version.

The uploaded tracking structure is implemented using a boolean slice. Since Go slices are zero-initialized, all entries begin as false.

The for loop is used instead of Python's while.

There are no integer overflow concerns because the constraints are small relative to Go's integer range.

Worked Examples

Example 1

Input:

["LUPrefix", "upload", "longest", "upload", "longest", "upload", "longest"]
[[4], [3], [], [1], [], [2], []]

Step-by-step trace

Operation	Uploaded Videos	longest_prefix	Explanation
Initialize	{}	0	No uploads yet
upload(3)	{3}	0	Video 1 missing
longest()	{3}	0	Return 0
upload(1)	{1,3}	1	Video 1 exists, video 2 missing
longest()	{1,3}	1	Return 1
upload(2)	{1,2,3}	3	Videos 1 through 3 now complete
longest()	{1,2,3}	3	Return 3

Detailed pointer movement

After upload(2):

Initial state:

longest_prefix = 1

Check:

uploaded[2] == True

Advance:

longest_prefix = 2

Check again:

uploaded[3] == True

Advance:

longest_prefix = 3

Check again:

uploaded[4] == False

Stop.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1) amortized	Each video advances the pointer at most once
Space	O(n)	Boolean array stores upload state

Although the upload method contains a while loop, the pointer only moves forward throughout the lifetime of the object. Since there are at most n total pointer increments, the total work across all operations is O(n).

This gives amortized constant time per operation.

Test Cases

# Example from problem statement
obj = LUPrefix(4)
obj.upload(3)
assert obj.longest() == 0  # video 1 missing

obj.upload(1)
assert obj.longest() == 1  # prefix [1]

obj.upload(2)
assert obj.longest() == 3  # prefix [1,2,3]

# Smallest possible input
obj = LUPrefix(1)
assert obj.longest() == 0  # nothing uploaded yet

obj.upload(1)
assert obj.longest() == 1  # entire stream uploaded

# Upload in order
obj = LUPrefix(5)
obj.upload(1)
assert obj.longest() == 1

obj.upload(2)
assert obj.longest() == 2

obj.upload(3)
assert obj.longest() == 3

# Upload completely out of order
obj = LUPrefix(5)
obj.upload(5)
obj.upload(4)
obj.upload(3)
assert obj.longest() == 0  # video 1 missing

obj.upload(1)
assert obj.longest() == 1  # video 2 missing

obj.upload(2)
assert obj.longest() == 5  # all videos now connected

# Missing middle element
obj = LUPrefix(6)
obj.upload(1)
obj.upload(2)
obj.upload(4)
obj.upload(5)

assert obj.longest() == 2  # video 3 missing

obj.upload(3)
assert obj.longest() == 5  # prefix extends immediately

# Large jump extension
obj = LUPrefix(7)

obj.upload(2)
obj.upload(3)
obj.upload(4)
obj.upload(5)
obj.upload(6)
obj.upload(7)

assert obj.longest() == 0  # video 1 missing

obj.upload(1)
assert obj.longest() == 7  # pointer jumps all the way

Test Summary

Test	Why
Problem statement example	Validates standard behavior
n = 1	Tests smallest boundary
Sequential uploads	Tests straightforward prefix growth
Reverse-order uploads	Tests delayed prefix formation
Missing middle element	Ensures prefix stops correctly
Large jump extension	Tests repeated pointer advancement

Edge Cases

Uploading videos completely out of order

A naive implementation may incorrectly assume uploads happen sequentially. For example:

upload(5)
upload(4)
upload(3)

The longest prefix must still remain 0 because video 1 is missing.

The implementation handles this correctly because the pointer only advances when the next required video exists.

Prefix extending by many positions at once

Consider:

upload(2)
upload(3)
upload(4)
upload(5)
upload(1)

When video 1 is finally uploaded, the prefix should immediately jump from 0 to 5.

The while loop correctly handles this by repeatedly advancing the pointer until the first missing video is found.

All videos uploaded

Once every video is uploaded, the pointer reaches n.

At that point:

longest_prefix = n

The implementation safely handles this because the boolean array is allocated with size n + 2, preventing out-of-bounds access when checking longest_prefix + 1.