LeetCode Problem 3815

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

Solution

LeetCode 3815 - Design Auction System

Problem Understanding

This problem asks us to design a real time auction system that supports inserting, updating, removing, and querying bids efficiently.

Each bid is uniquely identified by the pair (userId, itemId). A user may have at most one active bid for a particular item. If addBid is called again for the same user and item, the previous bid must be replaced.

The system must support four operations:

• Add a new bid.
• Update an existing bid.
• Remove an existing bid.
• Return the highest bidder for an item.

The most important part is the query operation. For a given itemId, we must find the user with:

1. The largest bid amount.
2. If multiple users have the same bid amount, the largest userId.

If an item has no bids, we return -1.

The input consists of a sequence of method calls on the AuctionSystem object. The output for each query operation is the result returned by that operation.

The constraints are important:

• Up to 5 * 10^4 total operations.
• bidAmount can be as large as 10^9.
• Multiple updates and removals may occur.

A naive implementation that scans all bids of an item every time we call getHighestBidder could become too slow if many bids exist for the same item.

There are several important edge cases:

• An item may have no bids at all.
• A user may add a bid for an item and later replace it with a different amount.
• Multiple users may have the same bid amount.
• Removing the current highest bidder should correctly reveal the next highest bidder.
• Updates may increase or decrease a bid amount.
• The problem guarantees that every updateBid and removeBid refers to an existing bid.

Approaches

Brute Force

The most straightforward solution is to store all bids for each item in a hash map:

itemId -> { userId -> bidAmount }

Adding, updating, and removing a bid can all be done in constant time.

However, when getHighestBidder(itemId) is called, we would need to scan every user bidding on that item and find the maximum according to:

(bidAmount, userId)

This guarantees correctness because we directly examine every active bid.

The problem is efficiency. If an item has k bids, each query costs O(k). In the worst case, many queries could repeatedly scan large collections of bids.

Key Insight

The expensive operation is finding the current maximum bid.

A max heap is a natural fit because it allows us to quickly retrieve the largest bid. The challenge is that heaps do not efficiently support arbitrary updates and deletions.

We solve this using lazy deletion.

For every item:

• Maintain a heap containing entries:

(−bidAmount, −userId, userId).

• Maintain a hash map of the currently active bids:

userId -> bidAmount.

Whenever a bid changes:

• Insert a new heap entry.
• Update the hash map.

Whenever a bid is removed:

• Delete it only from the hash map.

Old heap entries remain in the heap temporarily. When we query the highest bidder, we repeatedly remove heap entries that no longer match the current active state.

This is a standard lazy deletion technique that keeps all operations efficient.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Add/Update/Remove: O(1), Query: O(k)	O(n)	Scan all bids for an item whenever queried
Optimal	Add/Update/Remove: O(log k), Query: O(log k) amortized	O(n)	Heap plus lazy deletion

Here:

• k is the number of bids associated with a particular item.
• n is the total number of active and stale heap entries.

Algorithm Walkthrough

Data Structures

We maintain two structures.

For active bids:

item_bids[itemId][userId] = bidAmount

For ranking bids:

item_heaps[itemId]

Each heap entry stores:

(-bidAmount, -userId, userId)

Using negative values allows Python's min heap to behave as a max heap.

Steps

1. Create a hash map storing active bids for every item.
2. Create a heap for every item.
3. For addBid(userId, itemId, bidAmount):

• Update the active bid map.
• Push a new heap entry representing the bid.

4. For updateBid(userId, itemId, newAmount):

• Update the active bid amount.
• Push a new heap entry with the new value.
• The old heap entry becomes stale.

5. For removeBid(userId, itemId):

• Remove the user from the active bid map.
• Do not remove anything from the heap.
• Existing heap entries become stale.

6. For getHighestBidder(itemId):

• If the item has no active bids, return -1.
• Examine the heap top.
• Check whether the entry matches the current active bid.
• If it does not match, remove it and continue.
• Once a valid entry is found, return its userId.

Why it works

The active bid map always contains the true current state of the auction.

Whenever a bid changes, a fresh heap entry is inserted. Older entries remain in the heap but are marked implicitly as stale because they no longer match the active bid map.

During queries, stale entries are removed until the heap top corresponds to an active bid. Since the heap is ordered by (bidAmount, userId), the first valid entry encountered must be the correct highest bidder. Therefore every query returns the correct answer.

Python Solution

from collections import defaultdict
from heapq import heappush, heappop
from typing import Dict

class AuctionSystem:

    def __init__(self):
        self.item_bids: Dict[int, Dict[int, int]] = defaultdict(dict)
        self.item_heaps = defaultdict(list)

    def addBid(self, userId: int, itemId: int, bidAmount: int) -> None:
        self.item_bids[itemId][userId] = bidAmount
        heappush(
            self.item_heaps[itemId],
            (-bidAmount, -userId, userId)
        )

    def updateBid(self, userId: int, itemId: int, newAmount: int) -> None:
        self.item_bids[itemId][userId] = newAmount
        heappush(
            self.item_heaps[itemId],
            (-newAmount, -userId, userId)
        )

    def removeBid(self, userId: int, itemId: int) -> None:
        del self.item_bids[itemId][userId]

    def getHighestBidder(self, itemId: int) -> int:
        active_bids = self.item_bids[itemId]

        if not active_bids:
            return -1

        heap = self.item_heaps[itemId]

        while heap:
            neg_bid, _, user_id = heap[0]
            bid_amount = -neg_bid

            if (
                user_id in active_bids and
                active_bids[user_id] == bid_amount
            ):
                return user_id

            heappop(heap)

        return -1

The implementation uses two defaultdict objects.

item_bids stores the current valid bids. This is the authoritative source of truth.

item_heaps stores candidate highest bids. Every add or update inserts a new heap entry. We never attempt to locate and modify old entries inside the heap because that would be expensive.

When getHighestBidder is called, the heap top is repeatedly validated against the active bid map. If the entry no longer represents the user's current bid, it is discarded. Eventually the heap top becomes the true maximum active bid, which is returned immediately.

Go Solution

package main

import (
	"container/heap"
)

type Bid struct {
	amount int
	userId int
}

type MaxHeap []Bid

func (h MaxHeap) Len() int {
	return len(h)
}

func (h MaxHeap) Less(i, j int) bool {
	if h[i].amount != h[j].amount {
		return h[i].amount > h[j].amount
	}
	return h[i].userId > h[j].userId
}

func (h MaxHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *MaxHeap) Push(x interface{}) {
	*h = append(*h, x.(Bid))
}

func (h *MaxHeap) Pop() interface{} {
	old := *h
	n := len(old)
	item := old[n-1]
	*h = old[:n-1]
	return item
}

type AuctionSystem struct {
	itemBids  map[int]map[int]int
	itemHeaps map[int]*MaxHeap
}

func Constructor() AuctionSystem {
	return AuctionSystem{
		itemBids:  make(map[int]map[int]int),
		itemHeaps: make(map[int]*MaxHeap),
	}
}

func (this *AuctionSystem) AddBid(userId int, itemId int, bidAmount int) {
	if _, exists := this.itemBids[itemId]; !exists {
		this.itemBids[itemId] = make(map[int]int)
	}

	if _, exists := this.itemHeaps[itemId]; !exists {
		h := &MaxHeap{}
		heap.Init(h)
		this.itemHeaps[itemId] = h
	}

	this.itemBids[itemId][userId] = bidAmount
	heap.Push(this.itemHeaps[itemId], Bid{
		amount: bidAmount,
		userId: userId,
	})
}

func (this *AuctionSystem) UpdateBid(userId int, itemId int, newAmount int) {
	this.itemBids[itemId][userId] = newAmount

	heap.Push(this.itemHeaps[itemId], Bid{
		amount: newAmount,
		userId: userId,
	})
}

func (this *AuctionSystem) RemoveBid(userId int, itemId int) {
	delete(this.itemBids[itemId], userId)
}

func (this *AuctionSystem) GetHighestBidder(itemId int) int {
	activeBids, exists := this.itemBids[itemId]

	if !exists || len(activeBids) == 0 {
		return -1
	}

	h := this.itemHeaps[itemId]

	for h.Len() > 0 {
		top := (*h)[0]

		currentAmount, ok := activeBids[top.userId]

		if ok && currentAmount == top.amount {
			return top.userId
		}

		heap.Pop(h)
	}

	return -1
}

/**
 * Your AuctionSystem object will be instantiated and called as such:
 * obj := Constructor()
 * obj.AddBid(userId, itemId, bidAmount)
 * obj.UpdateBid(userId, itemId, newAmount)
 * obj.RemoveBid(userId, itemId)
 * param_4 := obj.GetHighestBidder(itemId)
 */

The Go implementation follows the same lazy deletion strategy. Since Go's standard library heap is customizable through the container/heap package, we implement a max heap by defining the Less function so that larger bids have higher priority. The tie breaker on userId is handled directly in the heap ordering.

Worked Examples

Example 1

Operations:

addBid(1, 7, 5)
addBid(2, 7, 6)
getHighestBidder(7)
updateBid(1, 7, 8)
getHighestBidder(7)
removeBid(2, 7)
getHighestBidder(7)
getHighestBidder(3)

State after each operation:

Operation	Active Bids for Item 7	Heap Contents (conceptually)	Result
addBid(1,7,5)	{1:5}	(5,1)	-
addBid(2,7,6)	{1:5, 2:6}	(6,2),(5,1)	-
getHighestBidder(7)	{1:5, 2:6}	valid top=(6,2)	2
updateBid(1,7,8)	{1:8, 2:6}	(8,1),(6,2),(5,1)	-
getHighestBidder(7)	{1:8, 2:6}	valid top=(8,1)	1
removeBid(2,7)	{1:8}	stale entries remain	-
getHighestBidder(7)	{1:8}	valid top=(8,1)	1
getHighestBidder(3)	empty	empty	-1

Notice that after updates and removals, stale heap entries remain. They are cleaned up only when they reach the heap top.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log k) amortized per operation	Heap insertion and lazy deletion each cost logarithmic time
Space	O(n)	Stores active bids plus stale heap entries

Each add or update inserts one heap entry, costing O(log k).

Each stale heap entry is removed at most once throughout the lifetime of the structure. Therefore the total cleanup work is proportional to the total number of inserted entries, giving amortized O(log k) query complexity.

The space complexity is O(n) because we store both active bids and historical heap entries waiting to be lazily removed.

Test Cases

# Example from statement
obj = AuctionSystem()
obj.addBid(1, 7, 5)
obj.addBid(2, 7, 6)
assert obj.getHighestBidder(7) == 2  # higher bid wins

obj.updateBid(1, 7, 8)
assert obj.getHighestBidder(7) == 1  # updated bid becomes highest

obj.removeBid(2, 7)
assert obj.getHighestBidder(7) == 1  # remaining bidder

assert obj.getHighestBidder(3) == -1  # item has no bids

# Tie on amount, larger userId wins
obj = AuctionSystem()
obj.addBid(1, 10, 100)
obj.addBid(5, 10, 100)
assert obj.getHighestBidder(10) == 5  # tie breaker

# Update decreases a bid
obj = AuctionSystem()
obj.addBid(1, 1, 100)
obj.addBid(2, 1, 90)
obj.updateBid(1, 1, 80)
assert obj.getHighestBidder(1) == 2  # highest changes

# Replacing an existing bid via addBid
obj = AuctionSystem()
obj.addBid(1, 1, 50)
obj.addBid(1, 1, 120)
assert obj.getHighestBidder(1) == 1  # replacement works

# Remove highest bidder
obj = AuctionSystem()
obj.addBid(1, 1, 100)
obj.addBid(2, 1, 90)
obj.removeBid(1, 1)
assert obj.getHighestBidder(1) == 2  # next highest becomes winner

# Single bidder removed
obj = AuctionSystem()
obj.addBid(3, 4, 500)
obj.removeBid(3, 4)
assert obj.getHighestBidder(4) == -1  # no bids remain

# Multiple stale entries
obj = AuctionSystem()
obj.addBid(1, 1, 10)
obj.updateBid(1, 1, 20)
obj.updateBid(1, 1, 30)
obj.updateBid(1, 1, 40)
assert obj.getHighestBidder(1) == 1  # stale heap entries ignored

# Multiple items tracked independently
obj = AuctionSystem()
obj.addBid(1, 1, 50)
obj.addBid(2, 2, 70)
assert obj.getHighestBidder(1) == 1  # item 1
assert obj.getHighestBidder(2) == 2  # item 2

Test Summary

Test	Why
Problem example	Validates basic functionality
Equal bids	Verifies userId tie breaker
Update decreases bid	Ensures ranking changes correctly
addBid replacement	Confirms replacement semantics
Remove highest bidder	Verifies next bidder becomes winner
Remove only bidder	Tests empty item handling
Many updates	Validates lazy deletion correctness
Multiple items	Confirms per-item isolation

Edge Cases

Multiple Users With Identical Highest Bids

A common bug is comparing only bid amounts and forgetting the tie breaker. If two users bid the same amount, the user with the larger userId must win. The heap ordering explicitly includes userId as the secondary sorting key, ensuring the correct bidder is returned.

Updating a Bid Many Times

A user may repeatedly update the same bid. This creates multiple outdated heap entries. A solution that attempts to use heap values directly without validation could return an obsolete bid. The lazy deletion check compares the heap entry against the current active bid map before accepting it, guaranteeing correctness.

Removing the Current Highest Bidder

When the highest bidder is removed, their heap entry still exists. Without cleanup, queries might incorrectly return the deleted bidder. During getHighestBidder, stale entries are removed until a valid active bid reaches the top, ensuring deleted bids never affect results.

Querying an Item With No Active Bids

An item may never have received a bid, or all bids may have been removed. In both situations the active bid map is empty. The implementation immediately returns -1, matching the required behavior.

Replacing a Bid Using addBid

The statement specifies that calling addBid for an existing (userId, itemId) pair replaces the previous bid. The implementation updates the active bid map and pushes a new heap entry. The old entry becomes stale and will eventually be discarded, preserving the correct state.