Longest Uploaded Prefix

Medium

Asked by:

13 views

Topics:

Arrays

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.

Example 1:

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 <= 10⁵
1 <= video <= n
All values of video are distinct.
At most 2 * 10⁵ calls in total will be made to upload and longest.
At least one call will be made to longest.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible value of any element in the `uploaded` array, and what is the maximum possible value of `n`?
If there are no files uploaded (i.e., the `uploaded` array is empty), should I return 0 or is there another specified default value?
Does the `uploaded` array contain only positive integers, or can it contain other data types, negative numbers, or zero?
Is the input array `uploaded` guaranteed to contain unique IDs, or can the same file ID be 'uploaded' multiple times?
Is the input `uploaded` array sorted in any way (e.g., by upload time), or can I assume the file uploads happen in a random order?

Brute Force Solution

Approach

The brute force approach is like trying every possible scenario. For this problem, it involves checking prefixes of uploaded files one by one to see how long the valid sequence is.

Here's how the algorithm would work step-by-step:

Start by checking if the first file upload was successful.
Then, check if the first and second file uploads were successful, one after the other.
Continue doing this, adding one more file upload to the sequence each time, and checking if all the uploads so far have been successful in the order they were uploaded.
Keep track of the longest sequence of successfully uploaded files you find this way.
Eventually, you will reach the end of the list of file uploads. The longest sequence you found is the answer.

Code Implementation

def longest_uploaded_prefix_brute_force(uploaded_files, number_of_files):
    longest_prefix = 0

    for i in range(1, number_of_files + 1):
        # Check each prefix of uploaded files.
        is_valid_prefix = True
        for j in range(1, i + 1):
            if j not in uploaded_files:
                is_valid_prefix = False
                break

        # If the prefix is valid, update the longest prefix.
        if is_valid_prefix:

            longest_prefix = i

    return longest_prefix

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates up to n times, where n is the number of uploaded files. In each iteration, it checks if the prefix of uploads up to that point is a consecutive sequence. This prefix check involves iterating over the elements of the prefix, which takes time proportional to the length of the prefix. In the worst-case scenario, where we have to check almost all prefixes, the cumulative cost is 1 + 2 + 3 + ... + n. This sum is equivalent to n(n+1)/2, representing approximately n squared divided by 2 operations. Therefore, the time complexity is O(n²).

Space Complexity

O(1) – The brute force approach, as described, primarily involves iteratively checking prefixes of uploaded file IDs. It requires keeping track of the longest sequence found so far, and possibly a temporary variable to indicate if the current prefix is valid. These temporary variables consume a constant amount of extra space, independent of the number of file uploads, N. Therefore, the space complexity is O(1).

Optimal Solution

Approach

The problem involves finding the longest sequence of uploaded file pieces that are contiguous. The optimal strategy involves keeping track of which pieces have been uploaded and efficiently determining the length of the longest starting sequence. It avoids repeatedly checking the same pieces.

Here's how the algorithm would work step-by-step:

Keep track of which file pieces have been successfully uploaded. A simple way is to mark them as you receive confirmation.
Start checking from the beginning of the file (the first piece).
See if the first piece has been uploaded. If not, you're done; the longest prefix is zero.
If the first piece is uploaded, move to the second piece and check if it's uploaded.
Continue this process, checking each subsequent piece in order.
Stop as soon as you find a piece that hasn't been uploaded.
The number of pieces you checked before finding the missing one is the length of the longest uploaded prefix.

Code Implementation

def longest_uploaded_prefix(number_of_files, uploaded_files):
    uploaded = [False] * (number_of_files + 1)
    
    for file_index in uploaded_files:
        uploaded[file_index] = True

    longest_prefix = 0
    
    # Start checking from the beginning of the file.
    for i in range(1, number_of_files + 1):
        # Stop if we find a piece that hasn't been uploaded.
        if not uploaded[i]:
            break
        longest_prefix += 1

    # The number of pieces checked is the length of longest prefix.
    return longest_prefix

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the file pieces, checking if each piece has been uploaded, starting from the first piece. In the worst-case scenario, all pieces are uploaded, and the algorithm checks all 'n' pieces. The check for each piece (determining if it's uploaded) is assumed to be an O(1) operation (e.g., using a hash set or a boolean array). Therefore, the overall time complexity is O(n).

Space Complexity

O(N) – The primary auxiliary space usage comes from tracking which file pieces have been uploaded. The most straightforward approach is to use a boolean array or set-like data structure where the index (or key) represents a file piece and the value indicates whether it has been uploaded. Therefore, if N is the number of file pieces, we need a boolean array or set that can store N values to track the uploaded status of each piece. This results in an auxiliary space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty 'uploaded' array	Return 0 immediately, as no prefix can be formed.
'uploaded' array with only one element	Return 0 if the element is not 1, otherwise return 1 if it is 1.
'uploaded' array with a large number of elements (close to maximum integer size)	Ensure the solution uses a data structure and algorithm with optimal time complexity to avoid timeouts, like a set.
'uploaded' array contains duplicate values	The set will only store unique uploaded IDs, so duplicates should not affect the correctness of the prefix calculation.
'uploaded' array contains out-of-order IDs (e.g., [3, 1, 2])	The algorithm should correctly identify that only ID 1 is uploaded first, then 2 when added, then 3 when added.
'uploaded' array missing some IDs in the expected sequence (e.g., [1, 3, 4])	The algorithm should correctly identify the longest contiguous prefix, stopping at 1 in this case since 2 is missing.
'uploaded' array with extreme boundary values (close to MAX_INT)	The algorithm should still work correctly as long as it correctly verifies all integers up to the uploaded value.
Very large N with memory usage considerations	Using a boolean array or set data structure should be efficient in space, but consider the constraints of the problem.

Null or empty 'uploaded' array

How to Handle:

Return 0 immediately, as no prefix can be formed.

'uploaded' array with only one element

How to Handle:

Return 0 if the element is not 1, otherwise return 1 if it is 1.

'uploaded' array with a large number of elements (close to maximum integer size)

How to Handle:

Ensure the solution uses a data structure and algorithm with optimal time complexity to avoid timeouts, like a set.

'uploaded' array contains duplicate values

How to Handle:

The set will only store unique uploaded IDs, so duplicates should not affect the correctness of the prefix calculation.

'uploaded' array contains out-of-order IDs (e.g., [3, 1, 2])

How to Handle:

The algorithm should correctly identify that only ID 1 is uploaded first, then 2 when added, then 3 when added.

'uploaded' array missing some IDs in the expected sequence (e.g., [1, 3, 4])

How to Handle:

The algorithm should correctly identify the longest contiguous prefix, stopping at 1 in this case since 2 is missing.

'uploaded' array with extreme boundary values (close to MAX_INT)

How to Handle:

The algorithm should still work correctly as long as it correctly verifies all integers up to the uploaded value.

Very large N with memory usage considerations

How to Handle:

Using a boolean array or set data structure should be efficient in space, but consider the constraints of the problem.