LeetCode 3885 - Design Event Manager

LeetCode Problem 3885

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Design, Heap (Priority Queue), Ordered Set

Solution

Problem Understanding

The problem asks us to design an EventManager class that manages a set of events, each identified by a unique eventId and associated with a priority. The manager must support two primary operations: updating the priority of an active event and retrieving the highest-priority active event, with ties broken by the smallest eventId. The events are considered active until they are removed through the pollHighest operation.

The input provides an initial list of events, and the operations are performed sequentially on this set. For each pollHighest, we must return the eventId of the active event with the highest priority, removing it from the active set. If multiple events have the same highest priority, the smallest eventId among them is returned. If no active events remain, we return -1.

Constraints are significant: up to 10^5 events and up to 10^5 operations. Event IDs and priorities can be as large as 10^9, meaning any solution must efficiently handle both high cardinality and high numeric ranges. A naive linear scan for every pollHighest would be too slow.

Key observations include: every updatePriority refers to an active event, eventIds are unique, and operations must respect the active state of events. Edge cases include polling when no events remain, multiple events with identical priorities, and frequent priority updates.

Approaches

Brute Force:

Store events in a simple list and, for each pollHighest, scan the list to find the highest-priority active event. Updating a priority would involve finding the event by ID and updating its value. This guarantees correctness but is inefficient because each pollHighest is O(n) and updatePriority is also O(n) in the worst case. Given up to 10^5 operations and 10^5 events, this approach can reach O(n^2) time, which is too slow.

Optimal Approach:

The key insight is to use a priority queue (heap) to efficiently access the highest-priority event. Because we need to remove arbitrary events and update priorities, we maintain a hash map from eventId to current priority to validate the heap's top element. The heap stores tuples of (-priority, eventId) so the default min-heap behaves as a max-heap with ties broken by smallest eventId.

When polling, we repeatedly remove the top element from the heap until we find one that matches the current priority in the hash map, ensuring outdated priorities are skipped. Updating priority simply updates the hash map and pushes a new tuple onto the heap. This guarantees both updatePriority and pollHighest run in O(log n) amortized time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n) per operation	O(n)	Linear scan for highest priority and updates
Optimal	O(log n) per operation	O(n)	Heap with lazy deletion and hash map for priority validation

Algorithm Walkthrough

1. Initialization: Create a hash map eventMap mapping eventId to priority for constant-time lookups. Initialize a max-heap storing tuples (-priority, eventId) to prioritize higher values and tie-break by smaller eventId. Push all initial events onto the heap.
2. Update Priority: When updatePriority(eventId, newPriority) is called, update eventMap[eventId] with newPriority and push (-newPriority, eventId) onto the heap. The heap may now contain outdated entries for this eventId.
3. Poll Highest: When pollHighest() is called, repeatedly pop the top element of the heap. Check if the negative priority matches the current priority in eventMap[eventId]. If it does, remove it from the map and return the eventId. If it does not match, it is an outdated entry and is ignored. If the heap becomes empty, return -1.

Why it works: The hash map ensures we only consider active events with their latest priorities. The heap guarantees we always access the maximum priority quickly. Lazy deletion avoids the complexity of removing arbitrary elements from a heap while maintaining O(log n) time per operation.

Python Solution

import heapq

class EventManager:

    def __init__(self, events: list[list[int]]):
        self.eventMap = {}  # Maps eventId -> current priority
        self.heap = []  # Max-heap storing (-priority, eventId)
        for eventId, priority in events:
            self.eventMap[eventId] = priority
            heapq.heappush(self.heap, (-priority, eventId))

    def updatePriority(self, eventId: int, newPriority: int) -> None:
        self.eventMap[eventId] = newPriority
        heapq.heappush(self.heap, (-newPriority, eventId))

    def pollHighest(self) -> int:
        while self.heap:
            negPriority, eventId = heapq.heappop(self.heap)
            currentPriority = self.eventMap.get(eventId)
            if currentPriority is None:
                continue  # Event already removed
            if currentPriority == -negPriority:
                del self.eventMap[eventId]
                return eventId
        return -1

The code initializes the hash map and heap in O(n log n) time. Each updatePriority pushes a new tuple and updates the hash map, while pollHighest pops elements until a valid event is found. Lazy deletion ensures outdated priorities do not interfere.

Go Solution

package main

import (
	"container/heap"
)

type Event struct {
	eventId  int
	priority int
}

type EventHeap []Event

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

type EventManager struct {
	eventMap map[int]int
	heap     EventHeap
}

func Constructor(events [][]int) EventManager {
	em := EventManager{
		eventMap: make(map[int]int),
		heap:     EventHeap{},
	}
	for _, e := range events {
		eventId, priority := e[0], e[1]
		em.eventMap[eventId] = priority
		em.heap = append(em.heap, Event{eventId, priority})
	}
	heap.Init(&em.heap)
	return em
}

func (this *EventManager) UpdatePriority(eventId int, newPriority int) {
	this.eventMap[eventId] = newPriority
	heap.Push(&this.heap, Event{eventId, newPriority})
}

func (this *EventManager) PollHighest() int {
	for this.heap.Len() > 0 {
		top := heap.Pop(&this.heap).(Event)
		curr, exists := this.eventMap[top.eventId]
		if !exists {
			continue
		}
		if curr == top.priority {
			delete(this.eventMap, top.eventId)
			return top.eventId
		}
	}
	return -1
}

Go implementation uses a custom heap type with the same lazy deletion principle. Differences include struct-based events and explicit heap initialization.

Worked Examples

Example 1 Trace:

Initial events: [[5,7],[2,7],[9,4]]

Operation	Heap Contents (priority, eventId)	eventMap	Result
pollHighest	[(7,2),(7,5),(4,9)]	{2:7,5:7,9:4}	2
updatePriority 9,7	[(7,5),(7,9),(7,2),(4,9)]	{5:7,9:7}	null
pollHighest	[(7,5),(7,9),(4,9)]	{5:7,9:7}	5
pollHighest	[(7,9),(4,9)]	{9:7}	9

Example 2 Trace:

Initial events: [[4,1],[7,2]]

Operation	Heap	eventMap	Result
pollHighest	[(2,7),(1,4)]	{4:1,7:2}	7
pollHighest	[(1,4)]	{4:1}	4
pollHighest	[]	{}	-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log n) per operation	Heap push/pop is logarithmic, hash map lookup is O(1)
Space	O(n)	Heap and hash map both store all active events

Using lazy deletion prevents expensive heap removals, allowing efficient handling of updates and polling even at large scale.

Test Cases

# Provided examples
obj = EventManager([[5,7