Min order

Leetcode problem https://leetcode.com/problems/min-stack/

Problem Description

Imagine you are a Front Office trader, whose job is to execute trades. To simplify things, you only trade a single stock, and the only input you receive for each trade is the amount.

As your Back Office is really impatient, you need to execute the trades in order, such that the last request you have received is executed first. Additionally, once in a while, your Back Office may ask you about th eminimal order you have, that is not executed yet.

Design a data structure, that can help you solve these tasks. Implement a data structure that supports the following operations:

- addOrder(int amount) : adds an order
- executeOrder() : executes an Order (according to the rules above) and returns the amount associated with it
- extractMinOrder() : returns the amount of the current minimal order, without executing it

For converience all amounts can be assumed to be integers.

Sample inputs - Expected outputs

Below extractMin refers to the extractMinOrder.

addOrder(13), addOrder(11), addOrder(9), addOrder(20)

extractMin() -> 9
executeOrder() -> 20
extractMin() -> 9
executeOrder() -> 9
extractMin() -> 11
addOrder(11)
extractMin() -> 11
executeOrder() -> 11
extractMin() -> 11
executeOrder() -> 11
extractMin() -> 13
executeOrder() -> 13

Solution (Python)

Use two stacks:

• order stack, which holds each added order
• min order stack, which holds minimum observed order

Complexities:

• add_order time complexity O(1), space complexity O(1)
• execute_order time complexity O(1), space complexity O(1)
• extract_min time complexity O(1), space complexity O(1)

order_stack = []
min_order_stack = []

def add_order(order_value: int):
	order_stack.append(order_value)
	min_order = order_value if len(min_order_stack) == 0 else min(min_order_stack[-1], order_value)
	min_order_stack.append(min_order)

def execute_order() -> int:
	min_order_stack.pop()
	return order_stack.pop()

def extract_min() -> int:
	return min_order_stack[-1]

Testing:

add_order(13); add_order(11); add_order(9); add_order(20)

extract_min() # 9
execute_order() # 20
extract_min() # 9
execute_order() # 9
extract_min() # 11
add_order(11)
extract_min() # 11
execute_order() # 11
extract_min() # 11
execute_order() # 11
extract_min() # 13
execute_order() # 13

I walked through some other test cases, edge cases and other types of input.

I also mentioned that I should raise an exception if the stack is empty in functions execute_order and extract_min.

The engineer was happy, and we moved towards the next question.