Cakes Fulfillment Stock

Overview

The problem asks us to simulate an inventory management process for three types of cakes. We are given an initial stock and a sequence of orders. The logic follows two specific rules:

1. Completion Check: An order is "fully completed" only if we currently have enough of all three cake types to satisfy the entire order.
2. Mandatory Deduction: Regardless of whether we had enough stock to "complete" the order, we must deduct the requested amounts from our stock. If an order asks for more than we have, the stock for that specific cake type simply drops to zero.

The goal is to count how many orders met the "fully completed" criteria. Since orders must be processed sequentially and the stock levels change after every single order, a straightforward simulation is the most effective approach.

Brute Force

Given that this problem involves a sequential simulation where each state depends on the previous one, the "brute force" approach is essentially the simulation itself. We iterate through the orders one by one, check the condition for completion, and update the stock levels.

def count_fulfilled_orders(stock: list[int], orders: list[list[int]]) -> int:
    fulfilled_count = 0
    
    for order in orders:
        # Check if the order can be fully completed
        can_complete = True
        for i in range(3):
            if stock[i] < order[i]:
                can_complete = False
                break
        
        if can_complete:
            fulfilled_count += 1
            
        # Mandatory deduction: stock[i] = max(0, stock[i] - order[i])
        for i in range(3):
            stock[i] = max(0, stock[i] - order[i])
            
    return fulfilled_count

• Time complexity: O(N) — We iterate through the list of $N$ orders exactly once, performing a constant number of operations (3) for each order.
• Space complexity: O(1) — We update the stock in-place and only use a single integer variable for the counter.

Optimal / Best Approach

The simulation used in the brute force is already optimal in terms of time complexity ($O(N)$), as we must examine every order at least once. We can refine the implementation for conciseness using Python's zip and all functions, though the underlying logic remains the same.

Note that since the stock is modified even for failed orders, we subtract the order from the stock and then "clamp" any negative values to zero using max(0, val).

def count_fulfilled_orders(stock: list[int], orders: list[list[int]]) -> int:
    count = 0
    
    for order in orders:
        # 1. Check if all 3 types are sufficient BEFORE deducting
        if all(stock[i] >= order[i] for i in range(3)):
            count += 1
        
        # 2. Deduct from stock as much as possible for every order
        for i in range(3):
            stock[i] = max(0, stock[i] - order[i])
            
    return count

• Time complexity: O(N) — Where $N$ is the number of orders. We process each order in constant time because the number of cake types is fixed at 3.
• Space complexity: O(1) — We use a constant amount of extra space regardless of the input size (assuming the input stock array can be modified).

Edge Cases

• Zero Stock: If the initial stock is [0, 0, 0], no order requesting a positive amount of cakes can be fulfilled, but the stock will remain [0, 0, 0] after deductions.
• Zero Orders: If an order is [0, 0, 0], it is technically fulfilled (since stock[i] >= 0 will always be true), and the stock remains unchanged.
• Large Quantities: The cake counts can be up to $10^9$. Python handles arbitrarily large integers automatically, so we don't need to worry about 32-bit integer overflow.
• Empty Orders List: If orders is empty, the function correctly returns 0.

Fast