3815. Design Auction System

Medium

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are asked to design an auction system that manages bids from multiple users in real time.

Each bid is associated with a userId, an itemId, and a bidAmount.

Implement the AuctionSystem class:

AuctionSystem(): Initializes the AuctionSystem object.
void addBid(int userId, int itemId, int bidAmount): Adds a new bid for itemId by userId with bidAmount. If the same userId already has a bid on itemId, replace it with the new bidAmount.
void updateBid(int userId, int itemId, int newAmount): Updates the existing bid of userId for itemId to newAmount. It is guaranteed that this bid exists.
void removeBid(int userId, int itemId): Removes the bid of userId for itemId. It is guaranteed that this bid exists.
int getHighestBidder(int itemId): Returns the userId of the highest bidder for itemId. If multiple users have the same highest bidAmount, return the user with the highest userId. If no bids exist for the item, return -1.

In short, the system needs to support four operations: adding a bid (replacing any existing bid by the same user on the same item), updating an existing bid to a new amount, removing an existing bid, and querying the highest bidder for a given item. When determining the highest bidder, the bid with the largest bidAmount wins; ties are broken by choosing the larger userId. If there are no active bids on an item, the query should return -1.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Design + Supporting Data Structures?

This problem maps to Design + Supporting Data Structures through a short path in the full flowchart.

Designing an auction system with add/update/remove/get-highest operations requires combining a hash table with an ordered set per item.

Open in Flowchart

Intuition

The core challenge of this problem is supporting two seemingly conflicting needs at the same time: we must be able to quickly find and modify a specific user's bid on an item, and we must also be able to quickly find the highest bidder for an item.

Let's think about what each requirement implies:

To handle addBid, updateBid, and removeBid, we need to know, for a given (userId, itemId) pair, what the current bid amount is. If we have to scan through all bids to find this, every operation becomes slow. A natural fix is to use a hash table keyed by user and item — something like users[userId][itemId] = bidAmount. This lets us look up, replace, or delete a user's bid on an item in O(1) time. This directly supports the "replace existing bid" rule in addBid and the lookups needed in updateBid and removeBid.
To handle getHighestBidder, we need the bid with the largest amount, and on ties, the largest userId. If we only kept a hash table, finding the maximum would require scanning every bid on the item each time. Instead, we want a structure that keeps bids sorted so the maximum is always available at the end. This is where an ordered set comes in: for each item, we maintain a sorted collection of bids.

The clever trick is in what we store inside the ordered set. By storing each bid as a tuple (bidAmount, userId), the natural sorting order does exactly what the problem wants for free:

Tuples are compared by the first element first, so bids are ordered by bidAmount.
When two bids have the same amount, the comparison falls back to the second element, userId.

So the last element in the sorted set is automatically the bid with the highest amount, breaking ties by the highest user ID — precisely the rule for getHighestBidder. Reading it is just ls[-1][1], and an empty set means we return -1.

Now the two structures work together. The users table tells us a user's old bid amount, which is exactly the key we need to locate and remove the corresponding (oldAmount, userId) tuple from the item's ordered set. Without knowing the old amount, we couldn't efficiently delete the entry from the sorted structure. So every update or removal becomes a clean "remove the old tuple, add the new tuple" pair of operations, keeping both structures consistent.

Finally, notice that addBid and updateBid are almost the same operation — both end with "set the user's amount and place a tuple in the sorted set." The only difference is that addBid must first clear any existing bid by the same user. By simply calling removeBid at the start of addBid when a previous bid exists, we reuse logic and guarantee no stale tuples are left behind.

Solution Approach

We use a combination of a Hash Table and an Ordered Set to support all four operations efficiently.

We maintain two data structures:

items: a hash table where items[itemId] is an ordered set (a SortedList). Each element is a tuple (bidAmount, userId). The set is sorted in ascending order, first by bidAmount and then by userId on ties. This makes the last element the highest bidder.
users: a hash table where users[userId][itemId] stores the current bid amount of that user on that item. This gives us O(1) lookup of any user's existing bid.

Let's walk through each operation.

addBid(userId, itemId, bidAmount)

If the user has no record yet, initialize self.users[userId] = {}.
If the user already has a bid on this item (itemId in self.users[userId]), call removeBid(userId, itemId) first to clear the old bid from both structures. This enforces the "replace it" rule.
Record the new amount in users with self.users[userId][itemId] = bidAmount.
Insert the tuple (bidAmount, userId) into the ordered set with self.items[itemId].add((bidAmount, userId)).

updateBid(userId, itemId, newAmount)

Look up the old amount from the hash table: oldAmount = self.users[userId][itemId].
Remove the stale tuple (oldAmount, userId) from the ordered set.
Add the new tuple (newAmount, userId) into the ordered set.
Update the hash table with self.users[userId][itemId] = newAmount.

Knowing oldAmount is essential here — without it, we couldn't locate the exact tuple to delete from the sorted set.

removeBid(userId, itemId)

Look up the old amount: oldAmount = self.users[userId][itemId].
Remove the tuple (oldAmount, userId) from the ordered set.
Delete the entry from users with self.users[userId].pop(itemId).

getHighestBidder(itemId)

Get the ordered set ls = self.items[itemId].
If it is empty, return -1.
Otherwise return ls[-1][1] — the userId of the last (largest) tuple, which is the highest bid, with ties already broken by the larger userId.

Complexity Analysis

Let n be the number of bids on a single item.

addBid, updateBid, and removeBid each perform a constant number of insert/delete operations on the ordered set, costing O(log n) per operation. Hash table lookups are O(1).
getHighestBidder reads the last element directly in O(1).

The total space is O(N), where N is the total number of active bids across all items, since each bid is stored once in users and once in items.

Example Walkthrough

Let's trace through a small sequence of operations to see how the hash table (users) and the ordered set (items) stay in sync.

We'll start with an empty AuctionSystem and run the following calls:

addBid(1, 100, 50)
addBid(2, 100, 50)
addBid(1, 100, 70)
getHighestBidder(100)   -> ?
updateBid(2, 100, 90)
getHighestBidder(100)   -> ?
removeBid(2, 100)
getHighestBidder(100)   -> ?
getHighestBidder(999)   -> ?

Step 1: addBid(1, 100, 50)

User 1 has no record yet, so initialize users[1] = {}.
User 1 has no existing bid on item 100, so no removal is needed.
Record users[1][100] = 50.
Insert tuple (50, 1) into items[100].

State:

users  = { 1: {100: 50} }
items  = { 100: [(50, 1)] }

Step 2: addBid(2, 100, 50)

Initialize users[2] = {}.
No existing bid by user 2 on item 100.
Record users[2][100] = 50.
Insert tuple (50, 2) into items[100].

The ordered set sorts by bidAmount first, then userId. Both bids are 50, so they sort by userId:

users  = { 1: {100: 50}, 2: {100: 50} }
items  = { 100: [(50, 1), (50, 2)] }

Step 3: addBid(1, 100, 70)

User 1 already has a bid on item 100 (100 in users[1]), so this triggers the "replace" rule:
- Internally call removeBid(1, 100): look up oldAmount = 50, remove tuple (50, 1) from the set, and pop users[1][100].
Now record the new bid: users[1][100] = 70.
Insert tuple (70, 1).

State:

users  = { 1: {100: 70}, 2: {100: 50} }
items  = { 100: [(50, 2), (70, 1)] }

Notice the old (50, 1) tuple is gone — no stale data remains.

Step 4: getHighestBidder(100)

items[100] is [(50, 2), (70, 1)], not empty.
Read the last element: (70, 1).
Return ls[-1][1] = 1.

Output: 1 (user 1 bids 70, the highest).

Step 5: updateBid(2, 100, 90)

Look up oldAmount = users[2][100] = 50.
Remove stale tuple (50, 2) from the set.
Add new tuple (90, 2).
Update users[2][100] = 90.

State:

users  = { 1: {100: 70}, 2: {100: 90} }
items  = { 100: [(70, 1), (90, 2)] }

Step 6: getHighestBidder(100)

Last element is (90, 2).
Return 2.

Output: 2 (user 2 now leads with 90).

Step 7: removeBid(2, 100)

Look up oldAmount = users[2][100] = 90.
Remove tuple (90, 2) from the set.
Pop users[2][100].

State:

users  = { 1: {100: 70}, 2: {} }
items  = { 100: [(70, 1)] }

Step 8: getHighestBidder(100)

Last element is (70, 1).
Return 1.

Output: 1 (only user 1 remains).

Step 9: getHighestBidder(999)

No bids have ever been placed on item 999, so its ordered set is empty.
Return -1.

Output: -1

Key takeaways from the trace

The users table always gave us the old amount needed to locate and delete the exact (amount, userId) tuple from the ordered set (steps 3, 5, 7) — without it, deletion from the sorted structure would be impossible to do efficiently.
The tuple ordering (bidAmount, userId) automatically handled the tie-break rule: in step 2, equal amounts of 50 sorted by userId, and the highest bidder is always just ls[-1][1].
addBid reused removeBid (step 3) to enforce the "replace" rule cleanly, ensuring both structures stayed consistent with no leftover tuples.

Solution Implementation

1from collections import defaultdict
2from sortedcontainers import SortedList
3
4
5class AuctionSystem:
6
7    def __init__(self) -> None:
8        # Maps item_id -> SortedList of (bid_amount, user_id) tuples,
9        # kept in ascending order so the last element is the highest bid.
10        self.items: dict[int, SortedList] = defaultdict(SortedList)
11        # Maps user_id -> {item_id: bid_amount}, tracking each user's current bids.
12        self.users: dict[int, dict[int, int]] = {}
13
14    def addBid(self, user_id: int, item_id: int, bid_amount: int) -> None:
15        # Ensure the user has an entry in the users mapping.
16        if user_id not in self.users:
17            self.users[user_id] = {}
18        # If the user already has a bid on this item, remove it first
19        # to avoid duplicate entries (treat as a re-bid).
20        if item_id in self.users[user_id]:
21            self.removeBid(user_id, item_id)
22        # Record the new bid for the user.
23        self.users[user_id][item_id] = bid_amount
24        # Insert the bid into the sorted list for the item.
25        self.items[item_id].add((bid_amount, user_id))
26
27    def updateBid(self, user_id: int, item_id: int, new_amount: int) -> None:
28        # Retrieve the user's existing bid amount on this item.
29        old_amount = self.users[user_id][item_id]
30        # Remove the stale (old_amount, user_id) entry from the sorted list.
31        self.items[item_id].remove((old_amount, user_id))
32        # Insert the updated (new_amount, user_id) entry.
33        self.items[item_id].add((new_amount, user_id))
34        # Update the user's recorded bid amount.
35        self.users[user_id][item_id] = new_amount
36
37    def removeBid(self, user_id: int, item_id: int) -> None:
38        # Look up the bid amount the user placed on this item.
39        old_amount = self.users[user_id][item_id]
40        # Remove the corresponding entry from the item's sorted list.
41        self.items[item_id].remove((old_amount, user_id))
42        # Drop the item from the user's bid record.
43        self.users[user_id].pop(item_id)
44
45    def getHighestBidder(self, item_id: int) -> int:
46        # Get the sorted list of bids for the requested item.
47        bids = self.items[item_id]
48        # If there are no bids, return -1; otherwise return the user_id
49        # of the last (highest) entry in the sorted list.
50        return -1 if not bids else bids[-1][1]
51
52
53# Your AuctionSystem object will be instantiated and called as such:
54# obj = AuctionSystem()
55# obj.addBid(user_id, item_id, bid_amount)
56# obj.updateBid(user_id, item_id, new_amount)
57# obj.removeBid(user_id, item_id)
58# param_4 = obj.getHighestBidder(item_id)
59

1import java.util.Comparator;
2import java.util.HashMap;
3import java.util.Map;
4import java.util.TreeSet;
5
6class AuctionSystem {
7
8    // Comparator that orders bids first by bid amount (ascending),
9    // then by user id (ascending) to break ties deterministically.
10    private static final Comparator<int[]> BID_COMPARATOR =
11        (firstBid, secondBid) -> firstBid[0] != secondBid[0]
12            ? Integer.compare(firstBid[0], secondBid[0])
13            : Integer.compare(firstBid[1], secondBid[1]);
14
15    // Maps each itemId to a sorted set of bids.
16    // Each bid is stored as int[]{bidAmount, userId}.
17    private final Map<Integer, TreeSet<int[]>> itemBids = new HashMap<>();
18
19    // Maps each userId to the bids that user has placed.
20    // The inner map associates an itemId with the user's current bid amount.
21    private final Map<Integer, Map<Integer, Integer>> userBids = new HashMap<>();
22
23    public AuctionSystem() {
24    }
25
26    /**
27     * Adds a bid for the given user on the given item.
28     * If the user already has a bid on this item, the existing bid is removed first.
29     */
30    public void addBid(int userId, int itemId, int bidAmount) {
31        // Ensure the user has a bid map.
32        Map<Integer, Integer> bidsForUser = userBids.computeIfAbsent(userId, key -> new HashMap<>());
33
34        // If the user already bid on this item, remove the old bid before adding the new one.
35        if (bidsForUser.containsKey(itemId)) {
36            removeBid(userId, itemId);
37        }
38
39        // Record the user's new bid amount for this item.
40        bidsForUser.put(itemId, bidAmount);
41
42        // Ensure the item has a sorted set of bids, then add the new bid.
43        TreeSet<int[]> bidsForItem = itemBids.computeIfAbsent(itemId, key -> new TreeSet<>(BID_COMPARATOR));
44        bidsForItem.add(new int[] {bidAmount, userId});
45    }
46
47    /**
48     * Updates an existing bid for the given user on the given item to a new amount.
49     */
50    public void updateBid(int userId, int itemId, int newAmount) {
51        // Retrieve the user's current bid amount on this item.
52        int oldAmount = userBids.get(userId).get(itemId);
53
54        // Replace the old bid entry with the new one in the item's sorted set.
55        TreeSet<int[]> bidsForItem = itemBids.get(itemId);
56        bidsForItem.remove(new int[] {oldAmount, userId});
57        bidsForItem.add(new int[] {newAmount, userId});
58
59        // Update the recorded bid amount for the user.
60        userBids.get(userId).put(itemId, newAmount);
61    }
62
63    /**
64     * Removes the bid placed by the given user on the given item.
65     */
66    public void removeBid(int userId, int itemId) {
67        // Retrieve the user's current bid amount on this item.
68        int oldAmount = userBids.get(userId).get(itemId);
69
70        // Remove the bid entry from the item's sorted set.
71        TreeSet<int[]> bidsForItem = itemBids.get(itemId);
72        bidsForItem.remove(new int[] {oldAmount, userId});
73
74        // Remove the item from the user's bid map.
75        userBids.get(userId).remove(itemId);
76    }
77
78    /**
79     * Returns the userId of the highest bidder for the given item,
80     * or -1 if there are no bids on the item.
81     */
82    public int getHighestBidder(int itemId) {
83        TreeSet<int[]> bidsForItem = itemBids.get(itemId);
84
85        // No bids exist for this item.
86        if (bidsForItem == null || bidsForItem.isEmpty()) {
87            return -1;
88        }
89
90        // The last element holds the highest bid; index 1 is the userId.
91        return bidsForItem.last()[1];
92    }
93}
94
95/**
96 * Your AuctionSystem object will be instantiated and called as such:
97 * AuctionSystem obj = new AuctionSystem();
98 * obj.addBid(userId,itemId,bidAmount);
99 * obj.updateBid(userId,itemId,newAmount);
100 * obj.removeBid(userId,itemId);
101 * int param_4 = obj.getHighestBidder(itemId);
102 */
103

1class AuctionSystem {
2    // Maps itemId -> ordered set of (bidAmount, userId) pairs.
3    // The set keeps bids sorted, so the largest element is the highest bid.
4    // Pairing with userId keeps entries unique even for equal bid amounts.
5    unordered_map<int, set<pair<int, int>>> items_;
6
7    // Maps userId -> (itemId -> bidAmount).
8    // Provides O(1) lookup of a user's current bid on a given item.
9    unordered_map<int, unordered_map<int, int>> users_;
10
11public:
12    AuctionSystem() {
13    }
14
15    // Add a new bid. If the user already has a bid on this item,
16    // the existing bid is removed first to avoid duplicates.
17    void addBid(int userId, int itemId, int bidAmount) {
18        if (users_[userId].count(itemId)) {
19            removeBid(userId, itemId);
20        }
21        // Record the bid in both index structures.
22        users_[userId][itemId] = bidAmount;
23        items_[itemId].insert({bidAmount, userId});
24    }
25
26    // Update an existing bid to a new amount.
27    // Assumes the user already has a bid on this item.
28    void updateBid(int userId, int itemId, int newAmount) {
29        auto userIt = users_.find(userId);
30        if (userIt == users_.end() || !userIt->second.count(itemId)) {
31            return; // No existing bid to update.
32        }
33
34        int oldAmount = userIt->second[itemId];
35        auto& itemSet = items_[itemId];
36
37        // Replace the old (amount, user) entry with the new one.
38        itemSet.erase({oldAmount, userId});
39        itemSet.insert({newAmount, userId});
40        userIt->second[itemId] = newAmount;
41    }
42
43    // Remove a user's bid on a given item from both index structures.
44    void removeBid(int userId, int itemId) {
45        auto userIt = users_.find(userId);
46        if (userIt == users_.end() || !userIt->second.count(itemId)) {
47            return; // Nothing to remove.
48        }
49
50        int oldAmount = userIt->second[itemId];
51
52        // Erase from the item's ordered set.
53        auto itemIt = items_.find(itemId);
54        if (itemIt != items_.end()) {
55            itemIt->second.erase({oldAmount, userId});
56        }
57
58        // Erase from the user's bid map.
59        userIt->second.erase(itemId);
60    }
61
62    // Return the userId with the highest bid on the item,
63    // or -1 if the item has no active bids.
64    int getHighestBidder(int itemId) {
65        auto it = items_.find(itemId);
66        if (it == items_.end() || it->second.empty()) {
67            return -1;
68        }
69        // rbegin() points to the largest (bidAmount, userId) pair;
70        // ".second" extracts the userId of that highest bid.
71        return it->second.rbegin()->second;
72    }
73};
74
75/**
76 * Your AuctionSystem object will be instantiated and called as such:
77 * AuctionSystem* obj = new AuctionSystem();
78 * obj->addBid(userId,itemId,bidAmount);
79 * obj->updateBid(userId,itemId,newAmount);
80 * obj->removeBid(userId,itemId);
81 * int param_4 = obj->getHighestBidder(itemId);
82 */
83

1// Maps itemId -> sorted array of [bidAmount, userId] pairs.
2// The array is kept sorted ascending, so the last element is the highest bid.
3// Pairing with userId keeps entries unique even for equal bid amounts.
4const items: Map<number, Array<[number, number]>> = new Map();
5
6// Maps userId -> (itemId -> bidAmount).
7// Provides O(1) lookup of a user's current bid on a given item.
8const users: Map<number, Map<number, number>> = new Map();
9
10// Compare two [bidAmount, userId] pairs the way C++ std::pair does:
11// first by bidAmount, then by userId as a tie-breaker.
12function comparePair(a: [number, number], b: [number, number]): number {
13    if (a[0] !== b[0]) {
14        return a[0] - b[0];
15    }
16    return a[1] - b[1];
17}
18
19// Find the index where the given pair is (or should be) located,
20// using binary search over the sorted array.
21function lowerBound(arr: Array<[number, number]>, target: [number, number]): number {
22    let lo = 0;
23    let hi = arr.length;
24    while (lo < hi) {
25        const mid = (lo + hi) >> 1;
26        if (comparePair(arr[mid], target) < 0) {
27            lo = mid + 1;
28        } else {
29            hi = mid;
30        }
31    }
32    return lo;
33}
34
35// Insert a pair into the sorted array, preserving ascending order.
36function insertSorted(arr: Array<[number, number]>, value: [number, number]): void {
37    const idx = lowerBound(arr, value);
38    arr.splice(idx, 0, value);
39}
40
41// Remove a pair from the sorted array if it exists.
42function eraseSorted(arr: Array<[number, number]>, value: [number, number]): void {
43    const idx = lowerBound(arr, value);
44    if (idx < arr.length && comparePair(arr[idx], value) === 0) {
45        arr.splice(idx, 1);
46    }
47}
48
49// Add a new bid. If the user already has a bid on this item,
50// the existing bid is removed first to avoid duplicates.
51function addBid(userId: number, itemId: number, bidAmount: number): void {
52    if (!users.has(userId)) {
53        users.set(userId, new Map());
54    }
55    const userBids = users.get(userId)!;
56
57    if (userBids.has(itemId)) {
58        removeBid(userId, itemId);
59    }
60
61    // Record the bid in both index structures.
62    userBids.set(itemId, bidAmount);
63    if (!items.has(itemId)) {
64        items.set(itemId, []);
65    }
66    insertSorted(items.get(itemId)!, [bidAmount, userId]);
67}
68
69// Update an existing bid to a new amount.
70// Assumes the user already has a bid on this item.
71function updateBid(userId: number, itemId: number, newAmount: number): void {
72    const userBids = users.get(userId);
73    if (userBids === undefined || !userBids.has(itemId)) {
74        return; // No existing bid to update.
75    }
76
77    const oldAmount = userBids.get(itemId)!;
78    const itemSet = items.get(itemId)!;
79
80    // Replace the old [amount, user] entry with the new one.
81    eraseSorted(itemSet, [oldAmount, userId]);
82    insertSorted(itemSet, [newAmount, userId]);
83    userBids.set(itemId, newAmount);
84}
85
86// Remove a user's bid on a given item from both index structures.
87function removeBid(userId: number, itemId: number): void {
88    const userBids = users.get(userId);
89    if (userBids === undefined || !userBids.has(itemId)) {
90        return; // Nothing to remove.
91    }
92
93    const oldAmount = userBids.get(itemId)!;
94
95    // Erase from the item's sorted array.
96    const itemSet = items.get(itemId);
97    if (itemSet !== undefined) {
98        eraseSorted(itemSet, [oldAmount, userId]);
99    }
100
101    // Erase from the user's bid map.
102    userBids.delete(itemId);
103}
104
105// Return the userId with the highest bid on the item,
106// or -1 if the item has no active bids.
107function getHighestBidder(itemId: number): number {
108    const itemSet = items.get(itemId);
109    if (itemSet === undefined || itemSet.length === 0) {
110        return -1;
111    }
112    // The last element is the largest [bidAmount, userId] pair;
113    // index [1] extracts the userId of that highest bid.
114    return itemSet[itemSet.length - 1][1];
115}
116

Time and Space Complexity

Time Complexity

The time complexity is analyzed per operation, where m denotes the number of bids associated with the current item:

addBid: This method may call removeBid if the bid already exists, which performs a remove on the SortedList in O(log m) time. It then inserts a new entry via add, which also takes O(log m) time. The dictionary operations (users lookups and assignments) take O(1). Hence, the overall time complexity is O(log m).
updateBid: This method performs one remove operation (O(log m)) followed by one add operation (O(log m)) on the SortedList. The dictionary updates take O(1). Thus, the time complexity is O(log m).
removeBid: This method performs a single remove on the SortedList, which takes O(log m), plus O(1) dictionary operations. Therefore, the time complexity is O(log m).
getHighestBidder: This method accesses the last element of the SortedList via indexing ls[-1], which takes O(log m) time for a SortedList (due to its internal block-based structure). So the time complexity is O(log m).

In summary, each operation takes O(log m) time, where m is the number of bids for the current item.

Space Complexity

The space complexity is O(n), where n is the total number of bids. The items dictionary stores each bid as a (bidAmount, userId) tuple within the SortedList structures, and the users dictionary stores each bid as a mapping from itemId to bidAmount. Both structures collectively hold at most n bid entries, giving a total space usage of O(n).

Common Pitfalls

Pitfall 1: Forgetting to remove the old bid before re-bidding in `addBid`

The most frequent mistake is treating addBid as a pure insertion without checking whether the user already has a bid on that item. If you skip the "replace" step, the user ends up with two tuples in the sorted list for the same item.

Why it's a problem:

def addBid(self, user_id, item_id, bid_amount):
    self.users[user_id][item_id] = bid_amount          # overwrites the hash table...
    self.items[item_id].add((bid_amount, user_id))     # ...but adds a SECOND tuple!

Now items[itemId] contains both (oldAmount, userId) and (newAmount, userId), but users[userId][itemId] only remembers the newest amount. The two structures are out of sync.

This causes a downstream crash: a later removeBid or updateBid reads old_amount from the hash table and calls self.items[item_id].remove((old_amount, user_id)). Only one of the two stale tuples gets removed (or worse, the amount no longer matches and remove raises a ValueError/KeyError), leaving a ghost bid that can win getHighestBidder forever.

Solution: Always reconcile both structures. The code correctly guards this:

if item_id in self.users[user_id]:
    self.removeBid(user_id, item_id)   # clear the stale tuple first
self.users[user_id][item_id] = bid_amount
self.items[item_id].add((bid_amount, user_id))

Pitfall 2: Storing tuples as `(userId, bidAmount)` instead of `(bidAmount, userId)`

The tie-breaking rule is "largest bidAmount wins; ties broken by larger userId." A SortedList orders tuples lexicographically, comparing the first element first. If you store (userId, bidAmount), sorting is dominated by userId, completely breaking the comparison logic.

Solution: Place the primary sort key first. With (bidAmount, userId), the last element ls[-1] is the maximum amount, and among equal amounts it is the maximum userId — exactly matching both tie-break requirements, for free.

Pitfall 3: Using `self.items[item_id]` directly inside `getHighestBidder` with a `defaultdict`

Because items is a defaultdict(SortedList), any access — including a read inside getHighestBidder — auto-creates an empty SortedList for items that never received a bid. This silently grows memory with phantom item entries.

bids = self.items[item_id]   # creates an empty SortedList if item_id is new

Solution: This is benign for correctness (the empty list still returns -1), but to avoid the silent insertion, query without mutating:

def getHighestBidder(self, item_id):
    bids = self.items.get(item_id)
    return -1 if not bids else bids[-1][1]

Using .get() returns None for unseen items and leaves the dictionary untouched.

Pitfall 4: Relying on `O(log n)` semantics from a plain `list` or `bisect`-only approach

A tempting "simplification" is to keep a Python list and call list.sort() after every mutation, or to scan the whole list in getHighestBidder for the max. The former is O(n log n) per write and the latter is O(n) per query — both degrade badly under heavy real-time bidding.

Solution: Use SortedList from sortedcontainers, which gives O(log n) add/remove and O(1) access to the last element via ls[-1]. This is what keeps every operation efficient as the auction scales.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering

3815. Design Auction System

Problem Description

How We Pick the Algorithm

Why Design + Supporting Data Structures?

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Common Pitfalls

Pitfall 1: Forgetting to remove the old bid before re-bidding in addBid

Pitfall 2: Storing tuples as (userId, bidAmount) instead of (bidAmount, userId)

Pitfall 3: Using self.items[item_id] directly inside getHighestBidder with a defaultdict

Pitfall 4: Relying on O(log n) semantics from a plain list or bisect-only approach

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Recommended Readings

Pitfall 1: Forgetting to remove the old bid before re-bidding in `addBid`

Pitfall 2: Storing tuples as `(userId, bidAmount)` instead of `(bidAmount, userId)`

Pitfall 3: Using `self.items[item_id]` directly inside `getHighestBidder` with a `defaultdict`

Pitfall 4: Relying on `O(log n)` semantics from a plain `list` or `bisect`-only approach