LeetCode 2254 - Design Video Sharing Platform

Certainly. Here is a complete, detailed technical solution guide for LeetCode 2254 - Design Video Sharing Platform, following your requested formatting and style. The problem asks us to design a class to simulate a video sharing platform.

leetcodehardhash-tabledesignheap-(priority-queue)

LeetCode Problem 2254

Difficulty: 🔴 Hard
Topics: Hash Table, Design, Heap (Priority Queue)

Solution

Certainly. Here is a complete, detailed technical solution guide for LeetCode 2254 - Design Video Sharing Platform, following your requested formatting and style.

Problem Understanding

The problem asks us to design a class to simulate a video sharing platform. Each video is represented as a string of digits, where each digit corresponds to the content at a specific minute. The platform needs to track views, likes, and dislikes for each video. Users can upload, remove, watch, like, dislike, and query statistics for a video.

A few key points about the platform:

  • Video IDs: When uploading, the platform assigns the smallest available integer videoId starting from 0. Deleted video IDs can be reused.
  • Watching a video: Returns a substring from startMinute to endMinute, inclusive. If endMinute exceeds video length, it is capped at video.length - 1.
  • Likes and dislikes: Each operation only affects the video if it exists; otherwise, queries return -1 or [-1].
  • Constraints: Each video can be up to 10^5 characters, the total length of all uploads is ≤ 10^5, and the number of operations is ≤ 10^5. This ensures our solution must be efficient, particularly for operations like finding the smallest available video ID.

Edge cases to consider include:

  • Removing or interacting with a non-existent video.
  • Watching with endMinute larger than video length.
  • Uploading after deletions (reuse of IDs).
  • Empty system at startup.

Approaches

Brute Force

A naive approach would use a list of videos, storing each video at its index equal to the video ID. Uploading a video would append to the list. To reuse IDs, we would need to scan for the first empty slot. Each removal would simply set the slot to None. Views, likes, and dislikes could be stored alongside the video string in a tuple or dictionary.

This works but has an O(n) upload in the worst case due to scanning for empty IDs, which is inefficient for 10^5 operations.

Optimal Approach

The key insight is that we need fast access to the smallest available videoId. Using a min-heap (priority queue) allows us to store available IDs and retrieve the smallest in O(log n) time. Meanwhile, we maintain a hash map (dictionary in Python, map in Go) mapping videoId to the video’s data (content, views, likes, dislikes).

Operations:

  • Upload: pop from min-heap or use the next new ID.
  • Remove: delete from hash map and push ID into min-heap.
  • Watch/like/dislike/get stats: directly use the hash map.

This approach ensures all operations run in O(log n) or O(1) time, which is acceptable for the constraints.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) per upload O(n) Scans list for smallest available ID
Optimal O(log n) per upload, O(1) other ops O(n) Uses hash map + min-heap for smallest available videoId

Algorithm Walkthrough

  1. Initialize the class with:
  • A hash map videos mapping videoId → video data (video, views, likes, dislikes).
  • A min-heap available_ids to track reusable video IDs.
  • A counter next_id for the next new videoId.
  1. Upload(video):
  • If available_ids is not empty, pop the smallest videoId. Otherwise, use next_id and increment it.
  • Store a dictionary containing the video string, views=0, likes=0, dislikes=0 in the hash map under the chosen videoId.
  • Return the videoId.
  1. Remove(videoId):
  • If videoId exists in the hash map, delete it and push the ID into available_ids.
  1. Watch(videoId, startMinute, endMinute):

  • If videoId exists:

  • Increment views.

  • Compute actual_end = min(endMinute, len(video)-1).

  • Return video[startMinute:actual_end+1].

  • Otherwise, return "-1".

  1. Like(videoId) / Dislike(videoId):
  • If videoId exists, increment likes or dislikes respectively. Otherwise, do nothing.
  1. GetLikesAndDislikes(videoId):
  • Return [likes, dislikes] if video exists; otherwise, [-1].
  1. GetViews(videoId):
  • Return views if video exists; otherwise, -1.

Why it works:

The hash map ensures O(1) access to video data for all operations except upload. The min-heap guarantees that each new video gets the smallest available ID, handling reuse efficiently. This design respects the constraints and supports the required queries efficiently.

Python Solution

from typing import List
import heapq

class VideoSharingPlatform:

    def __init__(self):
        self.videos = {}
        self.available_ids = []
        self.next_id = 0

    def upload(self, video: str) -> int:
        if self.available_ids:
            videoId = heapq.heappop(self.available_ids)
        else:
            videoId = self.next_id
            self.next_id += 1
        self.videos[videoId] = {'video': video, 'views': 0, 'likes': 0, 'dislikes': 0}
        return videoId

    def remove(self, videoId: int) -> None:
        if videoId in self.videos:
            del self.videos[videoId]
            heapq.heappush(self.available_ids, videoId)

    def watch(self, videoId: int, startMinute: int, endMinute: int) -> str:
        if videoId not in self.videos:
            return "-1"
        video_data = self.videos[videoId]
        video_data['views'] += 1
        actual_end = min(endMinute, len(video_data['video']) - 1)
        return video_data['video'][startMinute:actual_end + 1]

    def like(self, videoId: int) -> None:
        if videoId in self.videos:
            self.videos[videoId]['likes'] += 1

    def dislike(self, videoId: int) -> None:
        if videoId in self.videos:
            self.videos[videoId]['dislikes'] += 1

    def getLikesAndDislikes(self, videoId: int) -> List[int]:
        if videoId not in self.videos:
            return [-1]
        v = self.videos[videoId]
        return [v['likes'], v['dislikes']]

    def getViews(self, videoId: int) -> int:
        if videoId not in self.videos:
            return -1
        return self.videos[videoId]['views']

Explanation:

  • videos dictionary stores all video metadata.
  • available_ids min-heap allows efficient reuse of IDs.
  • Each operation modifies or queries the hash map in O(1) time except upload which is O(log n) due to the heap.

Go Solution

package main

import (
    "container/heap"
)

type VideoData struct {
    video    string
    views    int
    likes    int
    dislikes int
}

type MinHeap []int

func (h MinHeap) Len() int            { return len(h) }
func (h MinHeap) Less(i, j int) bool  { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x any)         { *h = append(*h, x.(int)) }
func (h *MinHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

type VideoSharingPlatform struct {
    videos       map[int]*VideoData
    availableIDs MinHeap
    nextID       int
}

func Constructor() VideoSharingPlatform {
    return VideoSharingPlatform{
        videos:       make(map[int]*VideoData),
        availableIDs: MinHeap{},
        nextID:       0,
    }
}

func (this *VideoSharingPlatform) Upload(video string) int {
    var videoId int
    if len(this.availableIDs) > 0 {
        videoId = heap.Pop(&this.availableIDs).(int)
    } else {
        videoId = this.nextID
        this.nextID++
    }
    this.videos[videoId] = &VideoData{video: video}
    return videoId
}

func (this *VideoSharingPlatform) Remove(videoId int) {
    if _, ok := this.videos[videoId]; ok {
        delete(this.videos, videoId)
        heap.Push(&this.availableIDs, videoId)
    }
}

func (this *VideoSharingPlatform) Watch(videoId int, startMinute int, endMinute int) string {
    data, ok := this.videos[videoId]
    if !ok {
        return "-1"
    }
    data.views++
    actualEnd := end