Design Event Manager solution and explanation
6 more videos on this problem
Leetcode 3885 | Design Event Manager | Leetcode weekly contest 495CodeWithMeGuys · 14:24 · 331 views
Design Event Manager | LeetCode 3885 | Lazy Heap | Weekly Contest 495 | Java Code | Developer CoderDeveloper Coder · 19:15 · 124 views
LeetCode 3885 | Design Event Manager | Heap + HashMap | Lazy Deletion Explained | JavaCode Kage · 8:41 · 116 views
LeetCode Problem 3885 | Design Event ManagerRepovive TV · 12:36 · 106 views
Leetcode 3885 | Design Event Manager | Weekly Contest 495 | C++ | Easy Explanation | HindiPushkar Sehrawat · 32:35 · 74 views
Leetcode 3885. Design Event ManagerExpertFunda · 21:06 · 44 views
Leetcode Weekly contest- 495 Q2 - Design Event ManagerUnbound Coder · 9:38 · 19 views
The problem
You are given an initial list of events, where each event has a unique eventId and a priority.
Implement the EventManager class:
EventManager(int[][] events)Initializes the manager with the given events, whereevents[i] = [eventIdi, priorityi].void updatePriority(int eventId, int newPriority)Updates the priority of the active event with ideventIdtonewPriority.int pollHighest()Removes and returns theeventIdof the active event with the highest priority. If multiple active events have the same priority, return the smallesteventIdamong them. If there are no active events, return -1.
An event is called active if it has not been removed by pollHighest().
Example 1:
Input:
["EventManager", "pollHighest", "updatePriority", "pollHighest", "pollHighest"]
[[[[5, 7], [2, 7], [9, 4]]], [], [9, 7], [], []]
Output:
[null, 2, null, 5, 9]
Explanation
EventManager eventManager = new EventManager([[5,7], [2,7], [9,4]]); // Initializes the manager with three eventseventManager.pollHighest(); // both events 5 and 2 have priority 7, so return the smaller id 2
eventManager.updatePriority(9, 7); // event 9 now has priority 7
eventManager.pollHighest(); // remaining highest priority events are 5 and 9, return 5
eventManager.pollHighest(); // return 9
Example 2:
Input:
["EventManager", "pollHighest", "pollHighest", "pollHighest"]
[[[[4, 1], [7, 2]]], [], [], []]
Output:
[null, 7, 4, -1]
Explanation
EventManager eventManager = new EventManager([[4,1], [7,2]]); // Initializes the manager with two eventseventManager.pollHighest(); // return 7
eventManager.pollHighest(); // return 4
eventManager.pollHighest(); // no events remain, return -1
Constraints:
1 <= events.length <= 105events[i] = [eventId, priority]1 <= eventId <= 1091 <= priority <= 109- All the values of
eventIdineventsare unique. 1 <= newPriority <= 109- For every call to
updatePriority,eventIdrefers to an active event. - At most
105calls in total will be made toupdatePriorityandpollHighest.
Approach overview
Problem Overview: Design a system that manages events and supports operations such as scheduling, removing, and retrieving events efficiently. The core challenge is keeping events ordered so queries like the next upcoming event can be answered quickly.
Approach 1: Unordered List Simulation (O(n) time per query, O(n) space)
The most direct implementation stores all events in a simple list or array. Each insertion appends to the list in O(1) time. When you need to find the next valid event or process events in order, you iterate through the entire list to locate the smallest valid timestamp or identifier. This makes queries O(n), which becomes expensive as the number of events grows. This approach is useful for understanding the requirements but does not scale well for large input sizes.
Approach 2: Sorted Set (Balanced BST) (O(log n) operations, O(n) space)
A more efficient design stores events inside a sorted set, typically implemented using a balanced binary search tree such as TreeSet in Java or ordered structures in C++ and Python. The key idea is to maintain events automatically sorted by their time or priority. When a new event is scheduled, you insert it into the sorted structure in O(log n). When an event is removed or completed, deletion also takes O(log n).
This ordering enables fast queries. If you need the earliest event, you simply read the first element of the sorted structure. If the problem requires locating the next event after a given timestamp, you perform a ceiling or lower_bound style lookup, which also runs in O(log n). The structure handles ordering automatically, eliminating the need for repeated scans.
The sorted set design works well because event managers naturally require ordered scheduling. By delegating ordering to a balanced tree, the implementation remains clean while guaranteeing predictable performance. This approach is closely related to techniques used in binary search over ordered data and tree-based structures discussed in data structures. Many implementations rely directly on a sorted set abstraction.
Recommended for interviews: The sorted set approach is the expected solution. Interviewers want to see that you recognize the need for ordered retrieval and choose a structure that supports insertion, deletion, and neighbor queries in O(log n). Starting with the brute force list demonstrates understanding of the problem, but switching to a balanced tree or sorted set shows strong algorithmic judgment.
Solution
We define a sorted set sl to store tuples of priority and id (-priority, eventId) for all active events, and a hash map d to store the priority of each event.
During initialization, we iterate over the given event list, add the tuple of priority and id for each event into the sorted set sl, and store each event's priority in the hash map d.
For the updatePriority(eventId, newPriority) operation, we first retrieve the old priority of the event from the hash map d, then remove the tuple of the old priority and event id from the sorted set sl, add the tuple of the new priority and event id into sl, and update the event's priority in d.
For the pollHighest() operation, we first check whether the sorted set sl is empty. If it is, return -1. Otherwise, we retrieve the event with the highest priority (i.e., the first element) from sl, remove its tuple, delete the event's priority information from d, and return the event's id.
In terms of time complexity, initialization takes O(n log n) time, where n is the number of initial events. Each call to updatePriority and pollHighest takes O(log n) time. The space complexity is O(n), where n is the number of active events.
class EventManager:
def __init__(self, events: list[list[int]]):
self.sl = SortedList()
self.d = {}
for eventId, priority in events:
self.sl.add((-priority, eventId))
self.d[eventId] = priority
def updatePriority(self, eventId: int, newPriority: int) -> None:
old_priority = self.d[eventId]
self.sl.remove((-old_priority, eventId))
self.sl.add((-newPriority, eventId))
self.d[eventId] = newPriority
def pollHighest(self) -> int:
if not self.sl:
return -1
eventId = self.sl.pop(0)[1]
self.d.pop(eventId)
return eventId
# Your EventManager object will be instantiated and called as such:
# obj = EventManager(events)
# obj.updatePriority(eventId,newPriority)
# param_2 = obj.pollHighest()class EventManager {
private TreeSet<int[]> sl;
private Map<Integer, Integer> d;
public EventManager(int[][] events) {
sl = new TreeSet<>((a, b) -> {
if (a[0] != b[0]) return a[0] - b[0];
return a[1] - b[1];
});
d = new HashMap<>();
for (int[] e : events) {
int eventId = e[0], priority = e[1];
sl.add(new int[] {-priority, eventId});
d.put(eventId, priority);
}
}
public void updatePriority(int eventId, int newPriority) {
int old = d.get(eventId);
sl.remove(new int[] {-old, eventId});
sl.add(new int[] {-newPriority, eventId});
d.put(eventId, newPriority);
}
public int pollHighest() {
if (sl.isEmpty()) {
return -1;
}
int[] top = sl.pollFirst();
int eventId = top[1];
d.remove(eventId);
return eventId;
}
}
/**
* Your EventManager object will be instantiated and called as such:
* EventManager obj = new EventManager(events);
* obj.updatePriority(eventId,newPriority);
* int param_2 = obj.pollHighest();
*/class EventManager {
public:
set<pair<int, int>> sl;
unordered_map<int, int> d;
EventManager(vector<vector<int>>& events) {
for (auto& e : events) {
int eventId = e[0], priority = e[1];
sl.insert({-priority, eventId});
d[eventId] = priority;
}
}
void updatePriority(int eventId, int newPriority) {
int old = d[eventId];
sl.erase({-old, eventId});
sl.insert({-newPriority, eventId});
d[eventId] = newPriority;
}
int pollHighest() {
if (sl.empty()) {
return -1;
}
auto it = sl.begin();
int eventId = it->second;
sl.erase(it);
d.erase(eventId);
return eventId;
}
};
/**
* Your EventManager object will be instantiated and called as such:
* EventManager* obj = new EventManager(events);
* obj->updatePriority(eventId,newPriority);
* int param_2 = obj->pollHighest();
*/import (
rbt "github.com/emirpasic/gods/v2/trees/redblacktree"
"cmp"
)
type pair struct{ p, id int }
type EventManager struct {
sl *rbt.Tree[pair, struct{}]
d map[int]int
}
func Constructor(events [][]int) EventManager {
sl := rbt.NewWith[pair, struct{}](func(a, b pair) int {
return cmp.Or(a.p-b.p, a.id-b.id)
})
d := make(map[int]int)
for _, e := range events {
eventId, priority := e[0], e[1]
sl.Put(pair{-priority, eventId}, struct{}{})
d[eventId] = priority
}
return EventManager{sl: sl, d: d}
}
func (this *EventManager) UpdatePriority(eventId int, newPriority int) {
old := this.d[eventId]
this.sl.Remove(pair{-old, eventId})
this.sl.Put(pair{-newPriority, eventId}, struct{}{})
this.d[eventId] = newPriority
}
func (this *EventManager) PollHighest() int {
if this.sl.Size() == 0 {
return -1
}
it := this.sl.Iterator()
it.First()
top := it.Key()
eventId := top.id
this.sl.Remove(top)
delete(this.d, eventId)
return eventId
}
/**
* Your EventManager object will be instantiated and called as such:
* obj := Constructor(events);
* obj.UpdatePriority(eventId,newPriority);
* param_2 := obj.PollHighest();
*/Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Unordered List Simulation | O(n) per query | O(n) | Small datasets or when event ordering is rarely queried |
| Sorted Set (Balanced BST) | O(log n) insert, delete, query | O(n) | General case where events must remain ordered and queries occur frequently |
Frequently asked questions
Is Design Event Manager easy or hard?
Design Event Manager is generally considered a medium difficulty problem. The logic is straightforward once you recognize the need for an ordered structure, but choosing the correct data structure and handling operations efficiently requires solid data structure knowledge.
Design Event Manager Python/Java solution
Python solutions often simulate a sorted set using bisect with a sorted list or third‑party ordered set libraries. Java uses TreeSet directly, while C++ uses std::set. Each provides O(log n) insertion, deletion, and neighbor lookup operations.
How to solve Design Event Manager in O(log n)?
Store all events inside a sorted structure such as a TreeSet, ordered set, or balanced BST. Each new event is inserted while maintaining order. Queries like finding the next event use ceiling or lower_bound operations, which run in O(log n).
What is the best approach for Design Event Manager?
The most efficient approach uses a Sorted Set or balanced binary search tree. This structure keeps events automatically ordered while supporting insertion, deletion, and lookup in O(log n) time. It allows quick retrieval of the earliest event or the next event after a given timestamp.
Is Design Event Manager asked at Google/Amazon/Meta?
Design-style data structure problems similar to this appear frequently in interviews at large companies such as Google, Amazon, and Meta. They test your ability to choose appropriate data structures for efficient insert, delete, and query operations.
What data structure is used in Design Event Manager?
A Sorted Set or balanced binary search tree is typically used. Examples include TreeSet in Java, std::set in C++, or ordered set implementations in Python and Go. These structures maintain elements in sorted order and support logarithmic operations.
What is the time complexity of Design Event Manager?
Using a Sorted Set implementation, inserting, deleting, or searching for an event takes O(log n) time. The space complexity is O(n) because all scheduled events must be stored. A naive list-based approach may require O(n) time per query.
