The Redemption That Exhausted Each Coupon Budget

Hard
121.

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 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

ColumnType
codevarchar
budgetint
launched_ondate

Primary key: code.

One row per coupon campaign.

Table: campaign_redemptions

ColumnType
redemption_idint
codevarchar
redeemed_atdatetime
discountint

Primary key: redemption_id.

One row per order a coupon was applied to; discount (rupees) is always positive and code is always a campaign.

Example

The rows must come back in the order shown.

coupon_campaigns

codebudgetlaunched_on
DIWALI50015002024-10-25
UPI502002024-10-25
FESTIVE2050002024-10-26

campaign_redemptions

redemption_idcoderedeemed_atdiscount
1DIWALI5002024-10-28 10:00:00500
2DIWALI5002024-10-28 11:30:00500
3UPI502024-10-28 11:30:0050
4DIWALI5002024-10-28 12:00:00500
5DIWALI5002024-10-28 12:05:00500
6UPI502024-10-28 12:00:0050
7UPI502024-10-28 13:00:0050
9UPI502024-10-28 13:00:0050
8UPI502024-10-28 13:00:0050
10FESTIVE202024-10-29 09:00:001200

Output

codebudgetredemption_idredeemed_atcumulative_discount
DIWALI500150042024-10-28 12:00:001500
UPI5020082024-10-28 13:00:00200
Read the hints, the editorial and the reference solution
-- Write your MySQL query below

Sign in to write, run and submit queries

A free account — no card, no trial clock. You come straight back here.

Run your query to see its result next to the expected one, example by example.

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

ColumnType
codevarchar
budgetint
launched_ondate

Primary key: code.

One row per coupon campaign.

Table: campaign_redemptions

ColumnType
redemption_idint
codevarchar
redeemed_atdatetime
discountint

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

codebudgetlaunched_on
DIWALI50015002024-10-25
UPI502002024-10-25
FESTIVE2050002024-10-26

campaign_redemptions

redemption_idcoderedeemed_atdiscount
1DIWALI5002024-10-28 10:00:00500
2DIWALI5002024-10-28 11:30:00500
3UPI502024-10-28 11:30:0050
4DIWALI5002024-10-28 12:00:00500
5DIWALI5002024-10-28 12:05:00500
6UPI502024-10-28 12:00:0050
7UPI502024-10-28 13:00:0050
9UPI502024-10-28 13:00:0050
8UPI502024-10-28 13:00:0050
10FESTIVE202024-10-29 09:00:001200

Output

codebudgetredemption_idredeemed_atcumulative_discount
DIWALI500150042024-10-28 12:00:001500
UPI5020082024-10-28 13:00:00200

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 code

Another 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 →