#2424

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Longest Uploaded Prefix

Calculate the longest continuous uploaded prefix in a video stream efficiently using a mix of binary search and data structures.

hash table binary search union find design binary indexed tree

Problem Statement

You are managing a stream of n videos numbered 1 to n. Each video can be uploaded in any order, and you must support queries to determine the longest continuous prefix of uploaded videos. Implement a system to handle these uploads and prefix queries efficiently.

Specifically, design the LUPrefix class where you can call upload(video) to mark a video as uploaded, and longest() to return the length of the longest prefix where all videos from 1 up to i have been uploaded. Consider the performance when handling a high volume of uploads and prefix queries.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

Input ["LUPrefix", "upload", "longest", "upload", "longest", "upload", "longest"] [[4], [3], [], [1], [], [2], []] Output [null, null, 0, null, 1, null, 3]

Explanation LUPrefix server = new LUPrefix(4); // Initialize a stream of 4 videos. server.upload(3); // Upload video 3. server.longest(); // Since video 1 has not been uploaded yet, there is no prefix. // So, we return 0. server.upload(1); // Upload video 1. server.longest(); // The prefix [1] is the longest uploaded prefix, so we return 1. server.upload(2); // Upload video 2. server.longest(); // The prefix [1,2,3] is the longest uploaded prefix, so we return 3.

Constraints

1 <= n <= 105
1 <= video <= n
All values of video are distinct.
At most 2 * 105 calls in total will be made to upload and longest.
At least one call will be made to longest.

Solution Approach

Boolean Array Tracking

Maintain an array of size n+1 where array[i] is true if video i has been uploaded. Update the array on each upload, then iterate from the last known prefix to find the new longest uploaded prefix efficiently.

Binary Search Over Prefix

Use binary search on the valid answer space from the last confirmed prefix to n. Check if all videos up to mid are uploaded. This reduces repeated linear scans and fits the binary search over valid answer pattern.

Union-Find Optimization

Treat each uploaded video as a node in a union-find structure to link consecutive uploaded videos. Query the root of video 1 to determine the current longest prefix. This handles fragmented uploads efficiently and avoids scanning the array repeatedly.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity ranges from O(1) per upload to O(log n) per longest query if using binary search or union-find path compression. Space complexity is O(n) for tracking uploaded videos.

What Interviewers Usually Probe

Ask about handling out-of-order uploads efficiently.
Probe whether prefix computation can avoid scanning all videos.
Check if candidate recognizes binary search over answer space pattern.

Common Pitfalls or Variants

Common pitfalls

Iterating from 1 to n for each query leads to TLE with large n.
Forgetting to mark videos as uploaded correctly in the tracking structure.
Assuming uploads are sequential and failing with out-of-order inputs.

Follow-up variants

Query the number of missing videos in a range instead of the prefix.
Support batch uploads and compute longest prefix after each batch.
Return all longest prefixes after a series of uploads instead of single queries.

FAQ

What is the main pattern behind Longest Uploaded Prefix?

The primary pattern is binary search over the valid answer space, ensuring efficient prefix computation without scanning all videos.

Can uploads be handled out of order?

Yes, the solution must support uploads in any order, tracking each video independently to update the longest prefix.

What data structures are most useful for this problem?

Boolean arrays, Hash Tables, and Union-Find structures efficiently track uploaded videos and compute the longest prefix.

How does binary search optimize longest prefix queries?

Instead of scanning sequentially, binary search finds the highest index where all videos are uploaded, reducing query time.

What is a common mistake when implementing LUPrefix?

A frequent error is assuming uploads are sequential and failing to handle gaps, which breaks the longest prefix calculation.

terminal

Solution

Solution 1: Simulation

We use a variable $r$ to record the current longest prefix of uploaded videos, and an array or hash table $s$ to record the videos that have been uploaded.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class LUPrefix:
    def __init__(self, n: int):
        self.r = 0
        self.s = set()

    def upload(self, video: int) -> None:
        self.s.add(video)
        while self.r + 1 in self.s:
            self.r += 1

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


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

Continue Practicing

#2426 number of pairs satisfying inequality #2353 design a food rating system #2349 design a number container system