The Redemption That Exhausted Each Coupon Budget
Each coupon campaign has a discount budget in rupees. Redemptions are applied in order of redeemed_at, then redemption_id; the campaign is exhausted by the…
- Difficulty: Hard
- Topics: Window Functions, Subqueries
- Dialect: MySQL
- Problem: #121
Problem statement
Each coupon campaign has a discount budget in rupees. Redemptions are applied in order of redeemed_at, then redemption_id; the campaign is exhausted by the first redemption at which the running total of discount reaches or passes the budget (finance then claws back the excess).
For every exhausted campaign return code, budget, redemption_id and redeemed_at of that redemption, and cumulative_discount — the running total including it. Campaigns that never reached their budget are not listed. Order by code.
Tables
Table: coupon_campaigns
| Column | Type |
|---|---|
| code | varchar |
| budget | int |
| launched_on | date |
Primary key: code.
One row per coupon campaign.
Table: campaign_redemptions
| Column | Type |
|---|---|
| redemption_id | int |
| code | varchar |
| redeemed_at | datetime |
| discount | int |
Primary key: redemption_id.
One row per order a coupon was applied to; discount (rupees) is always positive and code is always a campaign.
Examples
Example 1
coupon_campaigns
| code | budget | launched_on |
|---|---|---|
| DIWALI500 | 1500 | 2024-10-25 |
| UPI50 | 200 | 2024-10-25 |
| FESTIVE20 | 5000 | 2024-10-26 |
campaign_redemptions
| redemption_id | code | redeemed_at | discount |
|---|---|---|---|
| 1 | DIWALI500 | 2024-10-28 10:00:00 | 500 |
| 2 | DIWALI500 | 2024-10-28 11:30:00 | 500 |
| 3 | UPI50 | 2024-10-28 11:30:00 | 50 |
| 4 | DIWALI500 | 2024-10-28 12:00:00 | 500 |
| 5 | DIWALI500 | 2024-10-28 12:05:00 | 500 |
| 6 | UPI50 | 2024-10-28 12:00:00 | 50 |
| 7 | UPI50 | 2024-10-28 13:00:00 | 50 |
| 9 | UPI50 | 2024-10-28 13:00:00 | 50 |
| 8 | UPI50 | 2024-10-28 13:00:00 | 50 |
| 10 | FESTIVE20 | 2024-10-29 09:00:00 | 1200 |
Output
| code | budget | redemption_id | redeemed_at | cumulative_discount |
|---|---|---|---|---|
| DIWALI500 | 1500 | 4 | 2024-10-28 12:00:00 | 1500 |
| UPI50 | 200 | 8 | 2024-10-28 13:00:00 | 200 |
How to solve The Redemption That Exhausted Each Coupon Budget
Compute the running total of discounts per campaign in redemption order, then find the first row where it reaches the budget.
The running total is SUM(discount) OVER (PARTITION BY code ORDER BY redeemed_at, redemption_id ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW). Both details of the window matter. Without redemption_id in the ORDER BY, redemptions in the same second have no defined order. And without an explicit ROWS frame the default is RANGE, which treats rows with equal sort keys as peers and adds them all at once — UPI50's three redemptions at 13:00 in the example would jump from 100 to 250 together, and the crossing row would be ambiguous. With the frame, the total reaches 200 at redemption 8.
Filter cumulative_discount >= budget and take the earliest such row per code with ROW_NUMBER(). Since discounts are positive the running total only grows, so the crossing can also be identified locally: the total with the row reaches the budget but the total without it (cumulative - discount) does not. The correlated alternative uses that test with a subquery for the running sum — quadratic per campaign, but window-free. FESTIVE20 never reaches ₹5,000 and is not listed.
Reference solution (MySQL)
WITH running AS (
SELECT r.code, c.budget, r.redemption_id, r.redeemed_at,
SUM(r.discount) OVER (PARTITION BY r.code ORDER BY r.redeemed_at, r.redemption_id
ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS cumulative_discount
FROM campaign_redemptions r
JOIN coupon_campaigns c ON c.code = r.code
), crossed AS (
SELECT code, budget, redemption_id, redeemed_at, cumulative_discount,
ROW_NUMBER() OVER (PARTITION BY code ORDER BY redeemed_at, redemption_id) AS pos
FROM running
WHERE cumulative_discount >= budget
)
SELECT code, budget, redemption_id, redeemed_at, cumulative_discount
FROM crossed
WHERE pos = 1
ORDER BY codeAnother way
SELECT code, budget, redemption_id, redeemed_at, cumulative_discount FROM (
SELECT r.code, c.budget, r.redemption_id, r.redeemed_at, r.discount,
(SELECT SUM(x.discount) FROM campaign_redemptions x
WHERE x.code = r.code AND (x.redeemed_at < r.redeemed_at OR (x.redeemed_at = r.redeemed_at AND x.redemption_id <= r.redemption_id))) AS cumulative_discount
FROM campaign_redemptions r JOIN coupon_campaigns c ON c.code = r.code
) t
WHERE cumulative_discount >= budget AND cumulative_discount - discount < budget
ORDER BY code← Longest Daily Selling Streak per Seller · Overlapping Flash Sales on the Same Product →