LeetCode Problem 3822

Difficulty: 🟡 Medium
Topics: Hash Table, Design

Solution

LeetCode 3822 - Design Order Management System

Problem Understanding

This problem asks us to implement a small in-memory order management system that supports four operations on trading orders.

Each order has three attributes:

• orderId, a unique identifier
• orderType, either "buy" or "sell"
• price, an integer value

When an order is added, it becomes active. Orders remain active until they are canceled. The system must support updating the price of an active order and querying all active orders that share a particular (orderType, price) combination.

The required operations are:

• addOrder(orderId, orderType, price) creates a new active order.
• modifyOrder(orderId, newPrice) changes the price of an existing active order.
• cancelOrder(orderId) removes an active order from the system.
• getOrdersAtPrice(orderType, price) returns all active order IDs matching the specified type and price.

The returned order IDs can be in any order, which is an important observation because it means we do not need to maintain any particular ordering of orders.

The constraints are relatively small. The total number of operations is at most 2000, and order IDs are at most 2000. Even though a simple solution would pass these constraints, the problem is categorized as a design problem, so we should focus on organizing the data structures to support all operations efficiently.

There are several important observations and edge cases:

• An order may be modified multiple times.
• An order may be modified to the same price it already has.
• After modification, the order must be removed from its old price group and inserted into its new price group.
• After cancellation, the order must no longer appear in any query result.
• The problem guarantees that every modified or canceled order exists and is currently active.
• The order of returned IDs does not matter, which allows us to use sets for storage.

Approaches

Brute Force

A straightforward solution is to store every active order in a hash map keyed by orderId.

When getOrdersAtPrice(orderType, price) is called, we scan through every active order and collect those whose type and price match the query.

This approach is correct because every active order is checked exactly once, ensuring that all matching orders are returned.

The downside is that every query requires scanning all active orders. If many queries are performed, this repeated linear search becomes inefficient.

Optimal Approach

The key observation is that queries are always based on the pair:

(orderType, price)

Instead of searching all active orders each time, we can directly maintain a mapping from (orderType, price) to the set of active order IDs currently belonging to that group.

We also need a second mapping from orderId to its current order information. This allows us to quickly find an order's current type and price during modifications and cancellations.

Using these two hash tables gives us:

• O(1) insertion
• O(1) modification
• O(1) cancellation
• O(k) retrieval, where k is the number of matching orders returned

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Add: O(1), Modify: O(1), Cancel: O(1), Query: O(n)	O(n)	Scan all active orders for every query
Optimal	Add: O(1), Modify: O(1), Cancel: O(1), Query: O(k)	O(n)	Direct lookup by (orderType, price)

Here, n is the number of active orders and k is the number of orders returned by the query.

Algorithm Walkthrough

Optimal Data Structure Design

We maintain two hash maps:

1. orders

• Key: orderId
• Value: (orderType, price)

2. groups

• Key: (orderType, price)
• Value: set of active orderIds

Step-by-Step Algorithm

1. When adding an order, store its (orderType, price) information in orders. Then insert its ID into the corresponding set in groups.
2. When modifying an order, first retrieve its current (orderType, oldPrice) from orders.
3. Remove the order ID from the set corresponding to (orderType, oldPrice) because the order no longer belongs there.
4. Update the order's stored price in orders.
5. Insert the order ID into the set corresponding to (orderType, newPrice).
6. When canceling an order, retrieve its stored information from orders.
7. Remove the order ID from the corresponding group set.
8. Remove the order entry from orders entirely because it is no longer active.
9. When processing a query, look up the set associated with (orderType, price).
10. Convert that set into a list and return it. If the key does not exist, return an empty list.

Why it works

The core invariant is that every active order exists in exactly one group corresponding to its current (orderType, price) pair.

Whenever an order is added, modified, or canceled, both data structures are updated together. Therefore, at any moment, the set stored for a given (orderType, price) contains precisely the active order IDs matching that pair. As a result, getOrdersAtPrice always returns exactly the correct orders.

Python Solution

from collections import defaultdict
from typing import List

class OrderManagementSystem:

    def __init__(self):
        self.orders = {}
        self.groups = defaultdict(set)

    def addOrder(self, orderId: int, orderType: str, price: int) -> None:
        self.orders[orderId] = (orderType, price)
        self.groups[(orderType, price)].add(orderId)

    def modifyOrder(self, orderId: int, newPrice: int) -> None:
        orderType, oldPrice = self.orders[orderId]

        self.groups[(orderType, oldPrice)].remove(orderId)

        self.orders[orderId] = (orderType, newPrice)
        self.groups[(orderType, newPrice)].add(orderId)

    def cancelOrder(self, orderId: int) -> None:
        orderType, price = self.orders[orderId]

        self.groups[(orderType, price)].remove(orderId)
        del self.orders[orderId]

    def getOrdersAtPrice(self, orderType: str, price: int) -> List[int]:
        return list(self.groups.get((orderType, price), set()))

The implementation directly follows the design described above.

The orders dictionary stores the current state of every active order. This allows modifications and cancellations to immediately locate an order's current type and price.

The groups dictionary maps each (orderType, price) pair to a set of active order IDs. Using a set provides O(1) insertion and removal operations.

When an order is modified, we first remove it from its old group, update its stored information, and then insert it into its new group. This preserves the invariant that every active order belongs to exactly one matching group.

Queries become simple dictionary lookups followed by conversion of the stored set into a list.

Go Solution

type Order struct {
	orderType string
	price     int
}

type OrderManagementSystem struct {
	orders map[int]Order
	groups map[string]map[int]struct{}
}

func Constructor() OrderManagementSystem {
	return OrderManagementSystem{
		orders: make(map[int]Order),
		groups: make(map[string]map[int]struct{}),
	}
}

func makeKey(orderType string, price int) string {
	return orderType + "#" + strconv.Itoa(price)
}

func (this *OrderManagementSystem) AddOrder(orderId int, orderType string, price int) {
	this.orders[orderId] = Order{
		orderType: orderType,
		price:     price,
	}

	key := makeKey(orderType, price)

	if _, exists := this.groups[key]; !exists {
		this.groups[key] = make(map[int]struct{})
	}

	this.groups[key][orderId] = struct{}{}
}

func (this *OrderManagementSystem) ModifyOrder(orderId int, newPrice int) {
	order := this.orders[orderId]

	oldKey := makeKey(order.orderType, order.price)
	delete(this.groups[oldKey], orderId)

	order.price = newPrice
	this.orders[orderId] = order

	newKey := makeKey(order.orderType, newPrice)

	if _, exists := this.groups[newKey]; !exists {
		this.groups[newKey] = make(map[int]struct{})
	}

	this.groups[newKey][orderId] = struct{}{}
}

func (this *OrderManagementSystem) CancelOrder(orderId int) {
	order := this.orders[orderId]

	key := makeKey(order.orderType, order.price)

	delete(this.groups[key], orderId)
	delete(this.orders, orderId)
}

func (this *OrderManagementSystem) GetOrdersAtPrice(orderType string, price int) []int {
	key := makeKey(orderType, price)

	group, exists := this.groups[key]
	if !exists {
		return []int{}
	}

	result := make([]int, 0, len(group))

	for orderId := range group {
		result = append(result, orderId)
	}

	return result
}

The Go version uses two maps just like the Python solution. Since Go does not support tuple keys directly in maps without defining a custom struct, a string key of the form "buy#100" is used to represent the (orderType, price) pair.

Sets are represented using map[int]struct{} because Go does not have a built in set type.

When no matching group exists, the implementation returns an empty slice rather than nil, matching the expected LeetCode behavior.

Worked Examples

Example 1

Operations:

addOrder(1, "buy", 1)
addOrder(2, "buy", 1)
addOrder(3, "sell", 2)
getOrdersAtPrice("buy", 1)
modifyOrder(1, 3)
modifyOrder(2, 1)
getOrdersAtPrice("buy", 1)
cancelOrder(3)
cancelOrder(2)
getOrdersAtPrice("buy", 1)

State evolution:

Operation	orders	groups
Initial	{}	{}
add(1,buy,1)	{1:(buy,1)}	{(buy,1):{1}}
add(2,buy,1)	{1:(buy,1),2:(buy,1)}	{(buy,1):{1,2}}
add(3,sell,2)	{1:(buy,1),2:(buy,1),3:(sell,2)}	{(buy,1):{1,2},(sell,2):{3}}

Query:

Query	Result
getOrdersAtPrice("buy",1)	[1,2] or [2,1]

Modify order 1:

State
orders = {1:(buy,3),2:(buy,1),3:(sell,2)}
(buy,1) = {2}
(buy,3) = {1}
(sell,2) = {3}

Modify order 2:

State
orders = {1:(buy,3),2:(buy,1),3:(sell,2)}
(buy,1) = {2}
(buy,3) = {1}

Query:

Query	Result
getOrdersAtPrice("buy",1)	[2]

Cancel order 3:

State
orders = {1:(buy,3),2:(buy,1)}

Cancel order 2:

State
orders = {1:(buy,3)}
(buy,1) = {}

Final query:

Query	Result
getOrdersAtPrice("buy",1)	[]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1) average for add, modify, cancel, O(k) for query	Hash table operations are constant time on average
Space	O(n)	Every active order is stored once

The total storage is linear in the number of active orders. Each order appears once in the orders map and once in exactly one group set. Query time is proportional only to the number of matching orders returned, which is optimal because those IDs must be output anyway.

Test Cases

# Example from problem statement
oms = OrderManagementSystem()
oms.addOrder(1, "buy", 1)
oms.addOrder(2, "buy", 1)
oms.addOrder(3, "sell", 2)

assert set(oms.getOrdersAtPrice("buy", 1)) == {1, 2}  # two matching buy orders

oms.modifyOrder(1, 3)
oms.modifyOrder(2, 1)

assert oms.getOrdersAtPrice("buy", 1) == [2]  # only order 2 remains

oms.cancelOrder(3)
oms.cancelOrder(2)

assert oms.getOrdersAtPrice("buy", 1) == []  # no matching orders

# Single order add/query
oms = OrderManagementSystem()
oms.addOrder(100, "sell", 500)

assert oms.getOrdersAtPrice("sell", 500) == [100]  # basic insertion

# Modify to a different price
oms = OrderManagementSystem()
oms.addOrder(1, "buy", 10)

oms.modifyOrder(1, 20)

assert oms.getOrdersAtPrice("buy", 10) == []      # removed from old price
assert oms.getOrdersAtPrice("buy", 20) == [1]     # added to new price

# Modify to same price
oms = OrderManagementSystem()
oms.addOrder(1, "buy", 10)

oms.modifyOrder(1, 10)

assert oms.getOrdersAtPrice("buy", 10) == [1]     # still present

# Cancel order
oms = OrderManagementSystem()
oms.addOrder(1, "sell", 30)

oms.cancelOrder(1)

assert oms.getOrdersAtPrice("sell", 30) == []     # removed after cancel

# Multiple types at same price
oms = OrderManagementSystem()
oms.addOrder(1, "buy", 50)
oms.addOrder(2, "sell", 50)

assert oms.getOrdersAtPrice("buy", 50) == [1]     # buy only
assert oms.getOrdersAtPrice("sell", 50) == [2]    # sell only

# Multiple orders at same group
oms = OrderManagementSystem()
for i in range(1, 6):
    oms.addOrder(i, "buy", 100)

assert set(oms.getOrdersAtPrice("buy", 100)) == {1, 2, 3, 4, 5}  # group lookup

# Query nonexistent group
oms = OrderManagementSystem()

assert oms.getOrdersAtPrice("buy", 999) == []     # empty query result

Test Summary

Test	Why
Problem example	Validates all supported operations together
Single order add/query	Verifies basic insertion
Modify to different price	Ensures migration between groups
Modify to same price	Verifies no accidental deletion
Cancel order	Ensures removed orders are not returned
Same price, different types	Confirms type filtering works correctly
Many orders in one group	Tests grouping behavior
Nonexistent query	Verifies empty result handling

Edge Cases

Modifying an Order to the Same Price

A common bug is accidentally duplicating an order when the new price equals the old price. Since we remove the order from the old group before reinserting it, and the underlying container is a set, the order remains present exactly once. The implementation therefore handles this case correctly.

Multiple Orders Sharing the Same Price

Many orders may have identical (orderType, price) values. A solution that stores only a single order per price would fail. Using a set of order IDs for each group ensures all matching orders are tracked and returned.

Canceling an Order That Shares a Group with Others

When one order is canceled, other orders at the same price must remain unaffected. Because cancellation removes only the specific orderId from the corresponding set, every other order in that group remains active and queryable.

Querying a Nonexistent Price Group

A query may reference a (orderType, price) combination that has never existed or currently has no active orders. The implementation uses a dictionary lookup with a default empty set, causing an empty list to be returned safely without any errors.

Repeated Modifications

An order may be modified many times before being canceled. The design always removes the order from its old group and inserts it into its new group, guaranteeing that the order never appears in multiple price groups simultaneously. This preserves the core invariant of the data structure.