1571. Warehouse Manager - Leetcode Solution

Problem Description

The "Warehouse Manager" problem involves managing the inventory of a warehouse given a series of product shipments and orders. You are given two lists: deliveries and orders. Each list contains integers representing the quantity of items delivered to or ordered from the warehouse on each day. Your task is to determine the minimum number of days required to fulfill all the orders, assuming that you can only use the inventory that has been delivered up to each day, and you cannot fulfill an order with future deliveries. Key constraints include:

Each order must be fulfilled in the order it appears (no reordering or skipping).
You cannot use more inventory than what is available up to that day.
There is only one valid solution for the minimum number of days needed.

Thought Process

To solve this problem, we need to simulate the process of managing inventory over time. A brute-force approach might involve checking every possible combination of deliveries and orders, but this quickly becomes inefficient. Instead, we should focus on tracking the current inventory after each delivery and checking if we can fulfill the next order. If we can't fulfill an order on a given day, we wait for the next delivery. The main insight is that we don't need to backtrack: as soon as we have enough inventory to fulfill the next order, we do so and move to the next order. This greedy approach works because the orders must be fulfilled in order, and we can't use future deliveries to fulfill current orders.

Solution Approach

The solution can be broken down into the following steps:

Initialize two pointers: one for the deliveries list (let's call it i) and one for the orders list (j).
Maintain a variable inventory to keep track of the current stock.
Iterate through the deliveries list day by day:
- On each day, add the delivery to inventory.
- While the current order can be fulfilled (i.e., inventory >= orders[j]), subtract the order from inventory and move to the next order (j += 1).
- Continue this process until all orders are fulfilled or all deliveries are processed.
The answer is the number of days (the value of i) it took to fulfill all orders.

This approach uses a greedy algorithm and a simple queue-like simulation, which is efficient and easy to implement.

Example Walkthrough

Suppose we have the following example:

deliveries = [5, 3, 7, 2]
orders = [4, 2, 6, 3]

Let's walk through the process:

Day 1: Delivery = 5, Inventory = 5. Order[0] = 4 can be fulfilled. Inventory becomes 1. Move to Order[1]. Order[1] = 2 cannot be fulfilled yet (Inventory = 1).
Day 2: Delivery = 3, Inventory = 4. Order[1] = 2 can be fulfilled. Inventory becomes 2. Move to Order[2]. Order[2] = 6 cannot be fulfilled (Inventory = 2).
Day 3: Delivery = 7, Inventory = 9. Order[2] = 6 can be fulfilled. Inventory becomes 3. Move to Order[3]. Order[3] = 3 can be fulfilled. Inventory becomes 0. All orders fulfilled.

It took 3 days to fulfill all orders.

Time and Space Complexity

Brute-force approach: Would involve checking all combinations of deliveries and orders, resulting in exponential time complexity, which is impractical.
Optimized approach: Our greedy simulation iterates through each delivery and order at most once, leading to O(N + M) time complexity, where N is the number of deliveries and M is the number of orders.
Space complexity is O(1) (excluding input storage), as we only use a few variables for tracking indices and inventory.

Summary

The Warehouse Manager problem is efficiently solved using a greedy, simulation-based approach. By tracking inventory and fulfilling orders as soon as possible, we avoid unnecessary complexity. This method leverages the sequential nature of the problem and provides a clear, optimal solution with linear time complexity.

Code Implementation

def minDaysToFulfillOrders(deliveries, orders):
    inventory = 0
    order_idx = 0
    n = len(deliveries)
    for day in range(n):
        inventory += deliveries[day]
        while order_idx < len(orders) and inventory >= orders[order_idx]:
            inventory -= orders[order_idx]
            order_idx += 1
            if order_idx == len(orders):
                return day + 1
    return -1  # If not possible

int minDaysToFulfillOrders(vector<int>& deliveries, vector<int>& orders) {
    int inventory = 0, order_idx = 0, n = deliveries.size();
    for (int day = 0; day < n; ++day) {
        inventory += deliveries[day];
        while (order_idx < orders.size() && inventory >= orders[order_idx]) {
            inventory -= orders[order_idx];
            order_idx++;
            if (order_idx == orders.size()) return day + 1;
        }
    }
    return -1; // If not possible
}

public int minDaysToFulfillOrders(int[] deliveries, int[] orders) {
    int inventory = 0, orderIdx = 0, n = deliveries.length;
    for (int day = 0; day < n; day++) {
        inventory += deliveries[day];
        while (orderIdx < orders.length && inventory >= orders[orderIdx]) {
            inventory -= orders[orderIdx];
            orderIdx++;
            if (orderIdx == orders.length) return day + 1;
        }
    }
    return -1; // If not possible
}

function minDaysToFulfillOrders(deliveries, orders) {
    let inventory = 0, orderIdx = 0;
    for (let day = 0; day < deliveries.length; day++) {
        inventory += deliveries[day];
        while (orderIdx < orders.length && inventory >= orders[orderIdx]) {
            inventory -= orders[orderIdx];
            orderIdx++;
            if (orderIdx === orders.length) return day + 1;
        }
    }
    return -1; // If not possible
}

AlgoMap.io

Want Help Cracking FAANG?