LeetCode 1174 - Immediate Food Delivery II

The problem provides a Delivery table that records food delivery orders. Each row represents a single order placed by a customer. Along with the order date, each customer also specifies a preferred delivery date.

leetcodemediumdatabase

LeetCode Problem 1174

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

The problem provides a Delivery table that records food delivery orders. Each row represents a single order placed by a customer. Along with the order date, each customer also specifies a preferred delivery date. If the preferred delivery date is exactly the same as the order date, the order is considered an immediate order. Otherwise, it is considered a scheduled order.

The key detail in this problem is that we are not interested in all orders. We only care about the first order for each customer. The first order is defined as the order with the earliest order_date for that customer. The problem guarantees that every customer has exactly one first order, which means there are no ties for the earliest date.

After identifying the first order for every customer, we must determine how many of those first orders are immediate orders. The final result should be the percentage of customers whose first order was immediate, rounded to two decimal places.

The input is represented as a relational database table. The expected output is a single-row result containing one column named immediate_percentage.

Even though explicit constraints are not listed, the problem structure suggests that efficiency matters. A naive solution that repeatedly scans the table for each customer would become expensive for large datasets. This motivates using SQL aggregation and filtering techniques efficiently.

Several edge cases are important to recognize upfront. A customer may have only one order, which automatically becomes their first order. Some customers may have immediate first orders while others may not. It is also possible that all first orders are immediate or none are immediate. Another important guarantee is that each customer has exactly one earliest order date, which simplifies the logic because we do not need to handle ties.

Approaches

A brute-force approach would process each customer independently. For every customer, we could scan the entire table to find the minimum order_date, then scan again to retrieve the corresponding row and determine whether it is immediate. After processing all customers, we would count how many first orders are immediate and divide by the total number of customers.

This approach is correct because it explicitly identifies the earliest order for every customer and checks whether the preferred delivery date matches the order date. However, it is inefficient because the table may be scanned repeatedly for each customer.

The key insight for a better solution is that SQL is designed for grouped aggregation. Instead of repeatedly searching for each customer's first order, we can compute the earliest order date for every customer in a single grouped query. Once we have those first-order rows, we can directly compute the percentage of immediate deliveries using aggregation.

This approach avoids redundant scans and leverages SQL operations such as GROUP BY, joins, and aggregate functions efficiently.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Repeatedly scans the table for each customer
Optimal O(n log n) or O(n) depending on indexing O(n) Uses grouping and filtering to isolate first orders efficiently

Algorithm Walkthrough

  1. First, identify the earliest order date for each customer. This can be done using a subquery with GROUP BY customer_id and MIN(order_date).
  2. Next, join the original Delivery table with the subquery result. The join condition matches both the customer_id and the earliest order_date. This isolates the first order row for every customer.
  3. Once we have the first orders, determine whether each one is immediate. An order is immediate if order_date = customer_pref_delivery_date.
  4. Count how many first orders are immediate. In SQL, this can be done using a conditional aggregation with CASE WHEN.
  5. Divide the number of immediate first orders by the total number of first orders. Multiply by 100 to convert the ratio into a percentage.
  6. Round the result to two decimal places using the SQL ROUND function.

Why it works

The algorithm works because the subquery guarantees that only the earliest order date for each customer is selected. Since the problem guarantees that every customer has exactly one unique first order, the join correctly retrieves exactly one row per customer. From there, counting immediate orders and dividing by the total number of customers produces the required percentage.

Python Solution

LeetCode Database problems use SQL rather than executable Python code. However, for completeness, the logical equivalent in Python can be expressed as follows.

from typing import List, Dict

class Solution:
    def immediateFoodDeliveryPercentage(self, delivery: List[Dict]) -> float:
        first_orders = {}

        for order in delivery:
            customer_id = order["customer_id"]

            if (
                customer_id not in first_orders or
                order["order_date"] < first_orders[customer_id]["order_date"]
            ):
                first_orders[customer_id] = order

        immediate_count = 0

        for order in first_orders.values():
            if order["order_date"] == order["customer_pref_delivery_date"]:
                immediate_count += 1

        percentage = (immediate_count * 100) / len(first_orders)

        return round(percentage, 2)

The implementation first stores the earliest order for each customer in a dictionary keyed by customer_id. As each row is processed, the algorithm compares the current order date with the stored earliest date. If the current order is earlier, it replaces the stored one.

After collecting all first orders, the code iterates through them and counts how many are immediate deliveries. Finally, it computes the percentage and rounds the result to two decimal places.

The Python version mirrors the same logic that the SQL solution uses conceptually.

Go Solution

package main

import (
	"math"
	"time"
)

type Delivery struct {
	DeliveryID              int
	CustomerID              int
	OrderDate               string
	CustomerPrefDeliveryDate string
}

func immediateFoodDeliveryPercentage(deliveries []Delivery) float64 {
	firstOrders := make(map[int]Delivery)

	for _, order := range deliveries {
		currentDate, _ := time.Parse("2006-01-02", order.OrderDate)

		existing, exists := firstOrders[order.CustomerID]

		if !exists {
			firstOrders[order.CustomerID] = order
			continue
		}

		existingDate, _ := time.Parse("2006-01-02", existing.OrderDate)

		if currentDate.Before(existingDate) {
			firstOrders[order.CustomerID] = order
		}
	}

	immediateCount := 0

	for _, order := range firstOrders {
		if order.OrderDate == order.CustomerPrefDeliveryDate {
			immediateCount++
		}
	}

	percentage := (float64(immediateCount) * 100.0) / float64(len(firstOrders))

	return math.Round(percentage*100) / 100
}

The Go implementation follows the same overall structure as the Python version. Since Go does not have built-in date comparison for strings in this format without parsing, the solution uses the time package to compare dates safely.

A map is used to store the earliest order for each customer. The final percentage calculation uses float64 conversion to avoid integer division.

SQL Solution

SELECT
    ROUND(
        100.0 * SUM(
            CASE
                WHEN d.order_date = d.customer_pref_delivery_date THEN 1
                ELSE 0
            END
        ) / COUNT(*),
        2
    ) AS immediate_percentage
FROM Delivery d
JOIN (
    SELECT
        customer_id,
        MIN(order_date) AS first_order_date
    FROM Delivery
    GROUP BY customer_id
) first_orders
ON d.customer_id = first_orders.customer_id
AND d.order_date = first_orders.first_order_date;

The SQL solution first computes the earliest order date for each customer in the subquery. It then joins those results back to the Delivery table to retrieve the corresponding rows.

The CASE WHEN expression converts immediate orders into 1 and scheduled orders into 0. Summing these values gives the number of immediate first orders. Dividing by the total number of first orders and multiplying by 100.0 produces the required percentage.

The ROUND(..., 2) function ensures the result is formatted to two decimal places as required by the problem.

Worked Examples

Consider the example input:

delivery_id customer_id order_date customer_pref_delivery_date
1 1 2019-08-01 2019-08-02
2 2 2019-08-02 2019-08-02
3 1 2019-08-11 2019-08-12
4 3 2019-08-24 2019-08-24
5 3 2019-08-21 2019-08-22
6 2 2019-08-11 2019-08-13
7 4 2019-08-09 2019-08-09

First, determine the earliest order for each customer.

customer_id first_order_date
1 2019-08-01
2 2019-08-02
3 2019-08-21
4 2019-08-09

Next, retrieve the corresponding rows.

customer_id order_date preferred_date Immediate?
1 2019-08-01 2019-08-02 No
2 2019-08-02 2019-08-02 Yes
3 2019-08-21 2019-08-22 No
4 2019-08-09 2019-08-09 Yes

There are 2 immediate first orders out of 4 customers.

$$\frac{2}{4} \times 100 = 50.00$$

So the final result is:

immediate_percentage
50.00

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each row is processed a constant number of times
Space O(n) Storage for first-order tracking per customer

The grouped SQL query processes the table once to determine minimum dates and once more during the join. With proper indexing on customer_id and order_date, this performs efficiently in practice. The auxiliary storage is proportional to the number of distinct customers.

Test Cases

# Example case from the prompt
assert round(
    Solution().immediateFoodDeliveryPercentage([
        {
            "delivery_id": 1,
            "customer_id": 1,
            "order_date": "2019-08-01",
            "customer_pref_delivery_date": "2019-08-02"
        },
        {
            "delivery_id": 2,
            "customer_id": 2,
            "order_date": "2019-08-02",
            "customer_pref_delivery_date": "2019-08-02"
        },
        {
            "delivery_id": 5,
            "customer_id": 3,
            "order_date": "2019-08-21",
            "customer_pref_delivery_date": "2019-08-22"
        },
        {
            "delivery_id": 7,
            "customer_id": 4,
            "order_date": "2019-08-09",
            "customer_pref_delivery_date": "2019-08-09"
        }
    ]),
    2
) == 50.00  # Standard mixed case

assert Solution().immediateFoodDeliveryPercentage([
    {
        "delivery_id": 1,
        "customer_id": 1,
        "order_date": "2020-01-01",
        "customer_pref_delivery_date": "2020-01-01"
    }
]) == 100.0  # Single immediate order

assert Solution().immediateFoodDeliveryPercentage([
    {
        "delivery_id": 1,
        "customer_id": 1,
        "order_date": "2020-01-01",
        "customer_pref_delivery_date": "2020-01-02"
    }
]) == 0.0  # Single scheduled order

assert Solution().immediateFoodDeliveryPercentage([
    {
        "delivery_id": 1,
        "customer_id": 1,
        "order_date": "2020-01-01",
        "customer_pref_delivery_date": "2020-01-01"
    },
    {
        "delivery_id": 2,
        "customer_id": 1,
        "order_date": "2020-01-03",
        "customer_pref_delivery_date": "2020-01-03"
    }
]) == 100.0  # Later orders should not matter

assert Solution().immediateFoodDeliveryPercentage([
    {
        "delivery_id": 1,
        "customer_id": 1,
        "order_date": "2020-01-02",
        "customer_pref_delivery_date": "2020-01-02"
    },
    {
        "delivery_id": 2,
        "customer_id": 2,
        "order_date": "2020-01-01",
        "customer_pref_delivery_date": "2020-01-03"
    }
]) == 50.0  # Mixed immediate and scheduled
Test Why
Standard mixed example Verifies normal operation
Single immediate order Tests smallest valid input
Single scheduled order Verifies 0% result
Multiple orders for same customer Ensures only first order is considered
Mixed customer outcomes Confirms percentage calculation

Edge Cases

One important edge case occurs when every customer's first order is immediate. In this situation, the result should be exactly 100.00. Some implementations incorrectly perform integer division before multiplying by 100, which can truncate the decimal result. The solution avoids this by multiplying with 100.0, ensuring floating-point arithmetic.

Another important case is when no customer's first order is immediate. The correct result should be 0.00. A buggy implementation might accidentally count later immediate orders instead of restricting the calculation to first orders only. The join condition in the SQL solution guarantees that only first orders are evaluated.

A third edge case involves customers with multiple orders. A naive implementation might accidentally examine all rows and count any immediate order, even if it is not the first one. The solution correctly isolates only the earliest order date per customer before calculating the percentage, which prevents later orders from affecting the result.