2512. Longest Uploaded Prefix¶

Difficulty: Medium

2512. Longest Uploaded Prefix

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.

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.

Solution¶

class LUPrefix {
    private static long seg[];
    private HashSet<Integer> set;
    public LUPrefix(int n) {
        seg = new long[4 * ((int)(1e5 + 1)) + 1];
        set = new HashSet<>();
    }

    public void upload(int video) {
        if (set.contains(video)) return;
        set.add(video);
        update(0, 0, (int)(1e5), video, video);
    }

    public int longest() {
        int low = 0;
        int high = (int)(1e5);
        int ans = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (ok(mid)) {
                ans = mid;
                low = mid + 1;
            }
            else high = mid - 1;
        }
        return ans;
    }

    private boolean ok(int mid) {
        long current_sum = query(0 , 0 , (int)(1e5) , 0 , mid);
        long req_sum = mid * 1L * (mid + 1) / 2;
        if (req_sum == current_sum) return true;
        return false;
    }

    //Segment Tree Implementation;
    private static void update(int ind, int low, int high, int index, int val){
        if(low == high){
            seg[ind] = val;
            return;
        }
        int mid = low + (high - low) / 2;
        if(index <= mid) update(2 * ind + 1, low, mid, index, val);
        else update(2 * ind + 2, mid + 1, high ,index, val);
        seg[ind] = seg[2 * ind + 1] + seg[2 * ind + 2];

    }
    private static long query(int ind, int low, int high , int l, int r){
        if(low >= l && high <= r) return seg[ind];
        if(low > r || high < l) return 0;
        int mid = low + (high - low) / 2;
        long left = query(2 * ind + 1, low , mid, l, r);
        long right = query(2 * ind + 2, mid + 1, high , l, r);
        return left + right;
    }

}

/**
 * Your LUPrefix object will be instantiated and called as such:
 * LUPrefix obj = new LUPrefix(n);
 * obj.upload(video);
 * int param_2 = obj.longest();
 */

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here