Skip to main content
Talentd

Design Auction System - Solution & Explanation

MediumHash TableDesignHeap (Priority Queue)Ordered Set11 min readAsked at: Google
Practice this problem

Problem Statement

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.

 

Example 1:

Input:
["AuctionSystem", "addBid", "addBid", "getHighestBidder", "updateBid", "getHighestBidder", "removeBid", "getHighestBidder", "getHighestBidder"]
[[], [1, 7, 5], [2, 7, 6], [7], [1, 7, 8], [7], [2, 7], [7], [3]]

Output:
[null, null, null, 2, null, 1, null, 1, -1]

Explanation

AuctionSystem auctionSystem = new AuctionSystem(); // Initialize the Auction system
auctionSystem.addBid(1, 7, 5); // User 1 bids 5 on item 7
auctionSystem.addBid(2, 7, 6); // User 2 bids 6 on item 7
auctionSystem.getHighestBidder(7); // return 2 as User 2 has the highest bid
auctionSystem.updateBid(1, 7, 8); // User 1 updates bid to 8 on item 7
auctionSystem.getHighestBidder(7); // return 1 as User 1 now has the highest bid
auctionSystem.removeBid(2, 7); // Remove User 2's bid on item 7
auctionSystem.getHighestBidder(7); // return 1 as User 1 is the current highest bidder
auctionSystem.getHighestBidder(3); // return -1 as no bids exist for item 3

 

Constraints:

  • 1 <= userId, itemId <= 5 * 104
  • 1 <= bidAmount, newAmount <= 109
  • At most 5 * 104 total calls to addBid, updateBid, removeBid, and getHighestBidder.
  • The input is generated such that for updateBid and removeBid, the bid from the given userId for the given itemId will be valid.

Approach Overview

Problem Overview: Design a system that manages auction bids efficiently. You need to support operations such as placing a bid, updating or removing a bid, and retrieving the highest bidder. The system must keep bids ordered by value while allowing fast updates when the same bidder changes their bid.

Approach 1: Brute Force List Scan (O(n) time per query, O(n) space)

The simplest design stores all bids in a list or array. Each new bid is appended or updated by scanning the list for the bidder. When the highest bid is required, iterate through all stored bids and track the maximum value. This approach is straightforward but inefficient because every lookup or ranking operation requires a full scan. Time complexity becomes O(n) per query with O(n) space, which does not scale when the number of bidders grows.

Approach 2: Hash Table + Heap (Priority Queue) (O(log n) updates, O(n) space)

A more practical solution uses a hash table to store the latest bid for each bidder and a heap (priority queue) to track the highest bid. The heap stores pairs like (bidAmount, bidderId). When a bidder updates their bid, push the new value to the heap and update the hash map. While retrieving the top bid, discard stale entries whose value no longer matches the hash table. This keeps insertion and update operations at O(log n), while lookups remain efficient.

Approach 3: Hash Table + Ordered Set (O(log n) per operation)

The cleanest design uses a hash table combined with an ordered set (such as TreeSet in Java or balanced BST structures). The hash table maps bidderId → bidAmount so updates can be located instantly. The ordered set stores pairs sorted by bid amount (and optionally bidder id for tie-breaking). When a bidder updates their bid, remove the old pair from the ordered set and insert the new one. Retrieving the highest bidder becomes a constant-time lookup of the last element in the ordered structure. Each modification costs O(log n) time and the total space remains O(n).

Recommended for interviews: The Hash Table + Ordered Set design is typically expected. The brute-force version shows you understand the requirements, but interviewers want to see how you maintain ordering while supporting fast updates. Combining direct lookup from a hash table with ordered retrieval from a balanced tree demonstrates solid system design and data structure selection.

Solution

We define two hash tables. items is used to store all bid information for each item, where items[itemId] stores an ordered set. Each element in the set is a tuple (bidAmount, userId), representing a user's bid amount for that item. Since we need to quickly retrieve the user with the highest bid, this ordered set needs to be sorted by bid amount in ascending order. If bid amounts are identical, they are sorted by user ID in ascending order. The other hash table users is used to store the bid information of each user for each item, where users[userId][itemId] stores the user's bid amount for that item.

For the addBid(userId, itemId, bidAmount) operation, we first check if the user has already placed a bid on the item. If they have, we call the removeBid(userId, itemId) method to remove the original bid; then we add the new bid information to users and items.

For the updateBid(userId, itemId, newAmount) operation, we first retrieve the user's original bid amount for the item from users, then remove the corresponding tuple (oldAmount, userId) from items, add the new bid information to items, and update the bid amount in users.

For the removeBid(userId, itemId) operation, we first retrieve the user's original bid amount for the item from users, then remove the corresponding tuple (oldAmount, userId) from items, and finally delete the user's bid information for that item from users.

For the getHighestBidder(itemId) operation, we first check if items[itemId] is empty. If it is, we return -1; otherwise, we return the user ID of the last element in the ordered set, which corresponds to the highest bidder.

In terms of time complexity, each operation takes O(log m) time, where m is the number of bids for the current item. The space complexity is O(n), where n is the total number of bids.

Code

PythonJavaC++

Python

Java

C++

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force List ScanO(n) per queryO(n)Small datasets or quick prototype implementation
Hash Table + Heap (Priority Queue)O(log n) updates, amortized O(log n) retrievalO(n)When frequent highest-bid queries are needed with simple priority tracking
Hash Table + Ordered SetO(log n) per operationO(n)Best general solution when bids must stay fully ordered with efficient updates

Video Solution

Leetcode 3815 | Design Auction System | Leetcode Weekly contest 485 • CodeWithMeGuys • 424 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Design Auction System easy or hard?
Design Auction System is typically considered a medium-level problem. The main challenge is selecting the right combination of data structures to support both fast updates and ordered retrieval. Understanding hash tables, heaps, and ordered sets makes the solution straightforward.
Design Auction System Python/Java solution
In Python, the design can be implemented using a dictionary for bid storage and a sorted container or heap for ranking bids. In Java, HashMap combined with TreeSet provides a natural ordered-set implementation. Both maintain O(log n) updates and efficient retrieval of the highest bid.
How to solve Design Auction System in O(log n)?
Store bidder-to-bid mappings in a hash table for constant-time lookup. Maintain a sorted structure like TreeSet or balanced BST containing (bidAmount, bidderId). When a bid changes, remove the old pair from the ordered set and insert the updated one. Each modification costs O(log n) while keeping the highest bid instantly accessible.
What is the best approach for Design Auction System?
The most practical solution uses a hash table combined with an ordered set (balanced binary search tree). The hash table stores the current bid for each bidder, while the ordered set keeps bids sorted by value. This allows bid insertion, update, and removal in O(log n) time while retrieving the highest bidder in O(1) or O(log n) depending on the structure.
Is Design Auction System asked at Google/Amazon/Meta?
Design-style data structure problems involving heaps, ordered sets, and hash tables are common in interviews at companies like Amazon, Google, and Meta. Variants appear in system design or advanced data structure rounds where candidates must support efficient updates and ranking queries.
What data structure is used in Design Auction System?
The key structures are a hash table for fast bidder lookup and an ordered set or heap for maintaining sorted bids. The ordered set approach is often preferred because it supports deletion and reinsertion cleanly while preserving order in O(log n) time.
What is the time complexity of Design Auction System?
Using the optimal hash table plus ordered set design, each operation such as placing, updating, or removing a bid runs in O(log n) time due to tree rebalancing. Lookup of the highest bid is typically O(1) or O(log n). Space complexity is O(n) because all active bids must be stored.

Ready to solve this problem?

Practice Design Auction System with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Longest Substring Without Repeating Characters