LeetCode #3815 — MEDIUM

Design Auction System

Move from brute-force thinking to an efficient approach using hash map strategy.

Solve on LeetCode
The 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.
Patterns Used
🏗Design Patterns→📐Segment Tree→

Roadmap

  1. Brute Force Baseline
  2. Core Insight
  3. Algorithm Walkthrough
  4. Edge Cases
  5. Full Annotated Code
  6. Interactive Study Demo
  7. Complexity Analysis
Step 01

Brute Force Baseline

Problem summary: 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

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Hash Map · Design · Segment Tree

Example 1

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

Core Insight

What unlocks the optimal approach

  • Maintain a map from <code>itemId</code> to its active bids.
  • For each item, use a data structure ordered by <code>(bidAmount, userId)</code> to get the highest bidder efficiently.
  • On <code>addBid</code> or <code>updateBid</code>, remove the old entry (if any) and insert the new one.
  • On <code>removeBid</code>, delete the corresponding entry; return the top element for <code>getHighestBidder</code>.
Interview move: turn each hint into an invariant you can check after every iteration/recursion step.
Step 03

Algorithm Walkthrough

Iteration Checklist

  1. Define state (indices, window, stack, map, DP cell, or recursion frame).
  2. Apply one transition step and update the invariant.
  3. Record answer candidate when condition is met.
  4. Continue until all input is consumed.
Use the first example testcase as your mental trace to verify each transition.
Step 04

Edge Cases

Minimum Input
Single element / shortest valid input
Validate boundary behavior before entering the main loop or recursion.
Duplicates & Repeats
Repeated values / repeated states
Decide whether duplicates should be merged, skipped, or counted explicitly.
Extreme Constraints
Upper-end input sizes
Re-check complexity target against constraints to avoid time-limit issues.
Invalid / Corner Shape
Empty collections, zeros, or disconnected structures
Handle special-case structure before the core algorithm path.
Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #3815: Design Auction System
class AuctionSystem {
    private final Map<Integer, TreeSet<int[]>> items = new HashMap<>();
    private final Map<Integer, Map<Integer, Integer>> users = new HashMap<>();

    public AuctionSystem() {
    }

    public void addBid(int userId, int itemId, int bidAmount) {
        users.computeIfAbsent(userId, k -> new HashMap<>());

        if (users.get(userId).containsKey(itemId)) {
            removeBid(userId, itemId);
        }

        users.get(userId).put(itemId, bidAmount);

        items.computeIfAbsent(itemId,
            k
            -> new TreeSet<>(
                (a, b)
                    -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1])));

        items.get(itemId).add(new int[] {bidAmount, userId});
    }

    public void updateBid(int userId, int itemId, int newAmount) {
        int oldAmount = users.get(userId).get(itemId);
        TreeSet<int[]> set = items.get(itemId);

        set.remove(new int[] {oldAmount, userId});
        set.add(new int[] {newAmount, userId});

        users.get(userId).put(itemId, newAmount);
    }

    public void removeBid(int userId, int itemId) {
        int oldAmount = users.get(userId).get(itemId);
        TreeSet<int[]> set = items.get(itemId);

        set.remove(new int[] {oldAmount, userId});
        users.get(userId).remove(itemId);
    }

    public int getHighestBidder(int itemId) {
        TreeSet<int[]> set = items.get(itemId);
        if (set == null || set.isEmpty()) {
            return -1;
        }
        return set.last()[1];
    }
}

/**
 * Your AuctionSystem object will be instantiated and called as such:
 * AuctionSystem obj = new AuctionSystem();
 * obj.addBid(userId,itemId,bidAmount);
 * obj.updateBid(userId,itemId,newAmount);
 * obj.removeBid(userId,itemId);
 * int param_4 = obj.getHighestBidder(itemId);
 */
Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Press Step or Run All to begin.
Step 07

Complexity Analysis

Time
O(1) per op
Space
O(n)

Approach Breakdown

NAIVE
O(n) per op time
O(n) space

Use a simple list or array for storage. Each operation (get, put, remove) requires a linear scan to find the target element — O(n) per operation. Space is O(n) to store the data. The linear search makes this impractical for frequent operations.

OPTIMIZED DESIGN
O(1) per op time
O(n) space

Design problems target O(1) amortized per operation by combining data structures (hash map + doubly-linked list for LRU, stack + min-tracking for MinStack). Space is always at least O(n) to store the data. The challenge is achieving constant-time operations through clever structure composition.

Shortcut: Combine two data structures to get O(1) for each operation type. Space is always O(n).
Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Mutating counts without cleanup

Wrong move: Zero-count keys stay in map and break distinct/count constraints.

Usually fails on: Window/map size checks are consistently off by one.

Fix: Delete keys when count reaches zero.

Related Problems
#352Data Stream as Disjoint Intervalshard→#895Maximum Frequency Stackhard→#1348Tweet Counts Per Frequencymedium→#1912Design Movie Rental Systemhard→#2034Stock Price Fluctuation medium→