LeetCode 2474 - Customers With Strictly Increasing Purchases

The problem gives us an Orders table where each row represents a purchase made by a customer. Every order has an orderid, a customerid, an orderdate, and a price.

leetcodeharddatabase

LeetCode Problem 2474

Difficulty: 🔴 Hard
Topics: Database

Solution

Problem Understanding

The problem gives us an Orders table where each row represents a purchase made by a customer. Every order has an order_id, a customer_id, an order_date, and a price.

We need to find all customers whose yearly total purchases are strictly increasing from their first purchase year to their last purchase year.

The key detail is that we must consider every year in the range between the customer's first order year and last order year, even if the customer placed no orders in some years. For those missing years, the yearly purchase total is considered 0.

For example, suppose a customer placed orders in 2015 and 2017 only:

  • 2015 → 700
  • 2016 → 0
  • 2017 → 1000

The sequence becomes [700, 0, 1000], which is not strictly increasing because 0 is not greater than 700.

The phrase "strictly increasing" means every year's total must be larger than the previous year's total:

year_1 < year_2 < year_3 < ...

Equality is not allowed.

The input table may contain multiple orders for the same customer in the same year, so we must first aggregate yearly totals before checking the increasing condition.

The expected output is a table containing only the customer_id values that satisfy the condition.

An important observation is that gaps between years matter. A naive implementation might only compare years where purchases exist, but that would be incorrect because missing years must count as zero.

Some important edge cases include:

  • Customers with gaps between purchase years
  • Customers whose totals stay equal between years
  • Customers with decreasing totals
  • Customers with only one year of purchases
  • Multiple orders in the same year
  • Years with implicit zero totals due to no purchases

The problem guarantees that order_id is unique, so we do not need to handle duplicate rows.

Approaches

Brute Force Approach

A brute force solution would process each customer independently.

For every customer, we could:

  1. Extract all orders belonging to that customer.
  2. Determine the first and last purchase years.
  3. Build a complete list of years between those bounds.
  4. For each year, scan all orders again to compute the yearly total.
  5. Compare consecutive yearly totals to verify strict increase.

This approach is correct because it explicitly computes every required yearly total, including missing years that contribute 0.

However, it is inefficient because for each customer and each year, we repeatedly scan orders to recompute totals. If the table is large, this repeated scanning becomes expensive.

Key Insight

The important optimization is realizing that yearly totals should be aggregated only once.

Instead of repeatedly recalculating totals, we can:

  1. Group orders by (customer_id, year)
  2. Compute yearly sums once
  3. Use window functions such as LAG() to compare each year with the previous year
  4. Detect any violation of the strictly increasing condition

Another important insight is handling missing years correctly. Since missing years count as 0, we must generate all years between the first and last purchase years for every customer. This usually requires a recursive CTE or a numbers table.

Once every customer-year combination exists, the problem becomes a simple sequential comparison problem.

Approach Time Complexity Space Complexity Notes
Brute Force O(C × Y × N) O(Y) Repeatedly scans orders for each customer and year
Optimal O(N + C × Y) O(C × Y) Aggregates once and uses SQL window functions efficiently

Here:

  • N = number of orders
  • C = number of customers
  • Y = average number of years between first and last purchase

Algorithm Walkthrough

Optimal SQL Strategy

  1. First, aggregate all orders by customer and year.

We compute:

SUM(price)

grouped by:

customer_id, YEAR(order_date)

This gives us each customer's yearly purchase total. 2. Next, determine the first and last purchase year for every customer.

We compute:

MIN(year), MAX(year)

for each customer. 3. Generate every year between the first and last year.

This step is essential because missing years must count as zero purchases.

We use a recursive CTE to generate all intermediate years. 4. Join generated years with yearly totals.

Some generated years may not exist in the aggregated totals table. For those years, we use:

COALESCE(total, 0)

so missing years become zero. 5. Compare each year's total with the previous year's total.

We use the window function:

LAG(total)

partitioned by customer and ordered by year. 6. Detect violations.

If any year has:

current_total <= previous_total

then the customer fails the strictly increasing condition. 7. Return customers with no violations.

Why it works

The algorithm works because it explicitly constructs the exact sequence required by the problem definition:

  • every year between first and last purchase
  • including years with zero purchases

After constructing the sequence, the LAG() comparison checks every adjacent pair. A customer is valid if and only if every comparison satisfies strict increase.

Because every required year is represented exactly once, and every adjacent pair is checked exactly once, the solution is correct.

Python Solution

LeetCode Database problems are solved using SQL, but the following Python implementation demonstrates the same logic algorithmically.

from collections import defaultdict
from typing import List

class Solution:
    def strictlyIncreasingPurchases(
        self,
        orders: List[List[int]]
    ) -> List[int]:

        yearly_totals = defaultdict(lambda: defaultdict(int))

        for order_id, customer_id, year, price in orders:
            yearly_totals[customer_id][year] += price

        result = []

        for customer_id, year_map in yearly_totals.items():
            first_year = min(year_map.keys())
            last_year = max(year_map.keys())

            previous_total = -1
            valid = True

            for year in range(first_year, last_year + 1):
                current_total = year_map.get(year, 0)

                if current_total <= previous_total:
                    valid = False
                    break

                previous_total = current_total

            if valid:
                result.append(customer_id)

        return result

Implementation Explanation

The solution uses a nested dictionary structure:

yearly_totals[customer_id][year]

to store the total purchases for every customer-year pair.

The first loop aggregates yearly totals by summing prices.

Next, for each customer, we determine the first and last purchase years. These bounds define the exact range of years that must be checked.

The loop:

for year in range(first_year, last_year + 1):

ensures that missing years are included automatically.

When a year does not exist in the dictionary:

year_map.get(year, 0)

returns 0, matching the problem requirements.

The variable previous_total stores the prior year's total. If the current year's total is not strictly greater, the customer becomes invalid immediately.

Finally, all valid customer IDs are returned.

Go Solution

package main

import "sort"

type Order struct {
	OrderID    int
	CustomerID int
	Year       int
	Price      int
}

func strictlyIncreasingPurchases(orders []Order) []int {
	yearlyTotals := map[int]map[int]int{}

	for _, order := range orders {
		customer := order.CustomerID
		year := order.Year

		if yearlyTotals[customer] == nil {
			yearlyTotals[customer] = map[int]int{}
		}

		yearlyTotals[customer][year] += order.Price
	}

	result := []int{}

	for customer, yearMap := range yearlyTotals {
		firstYear := int(^uint(0) >> 1)
		lastYear := -1

		for year := range yearMap {
			if year < firstYear {
				firstYear = year
			}

			if year > lastYear {
				lastYear = year
			}
		}

		prevTotal := -1
		valid := true

		for year := firstYear; year <= lastYear; year++ {
			currentTotal := yearMap[year]

			if currentTotal <= prevTotal {
				valid = false
				break
			}

			prevTotal = currentTotal
		}

		if valid {
			result = append(result, customer)
		}
	}

	sort.Ints(result)

	return result
}

Go-specific Notes

The Go solution mirrors the Python logic closely.

A nested map is used instead of Python's defaultdict:

map[int]map[int]int

In Go, reading a nonexistent key from a map returns the zero value automatically, which is useful because missing years should count as 0.

The solution initializes missing inner maps manually because Go does not automatically create nested maps.

The result is sorted before returning so the output order is deterministic.

Worked Examples

Example 1

Input:

Customer 1:
2019 -> 1100 + 1200
2020 -> 3000
2021 -> 3100
2022 -> 4700

Step 1: Aggregate yearly totals

Customer Year Total
1 2019 2300
1 2020 3000
1 2021 3100
1 2022 4700

Step 2: Determine range

Customer First Year Last Year
1 2019 2022

Step 3: Compare sequentially

Year Total Previous Strictly Increasing?
2019 2300 -1 Yes
2020 3000 2300 Yes
2021 3100 3000 Yes
2022 4700 3100 Yes

Customer 1 is included.

Customer 2

Aggregated totals:

Year Total
2015 700
2017 1000

Generated range:

2015, 2016, 2017

Filled totals:

Year Total
2015 700
2016 0
2017 1000

Comparison:

Year Total Previous Valid
2015 700 -1 Yes
2016 0 700 No

Customer 2 is excluded immediately.

Customer 3

Year Total
2017 900
2018 900

Comparison:

Year Total Previous Valid
2017 900 -1 Yes
2018 900 900 No

Totals are equal, not strictly increasing.

Complexity Analysis

Measure Complexity Explanation
Time O(N + C × Y) Aggregate orders once, then scan yearly ranges
Space O(C × Y) Stores yearly totals for all customer-year pairs

The aggregation phase processes every order exactly once, which costs O(N).

The validation phase iterates through every year between each customer's first and last purchase years. If the average range size is Y, this costs O(C × Y) overall.

The space complexity comes from storing yearly totals in nested hash maps.

Test Cases

from collections import defaultdict

class Solution:
    def strictlyIncreasingPurchases(self, orders):
        yearly_totals = defaultdict(lambda: defaultdict(int))

        for order_id, customer_id, year, price in orders:
            yearly_totals[customer_id][year] += price

        result = []

        for customer_id, year_map in yearly_totals.items():
            first_year = min(year_map.keys())
            last_year = max(year_map.keys())

            previous_total = -1
            valid = True

            for year in range(first_year, last_year + 1):
                current_total = year_map.get(year, 0)

                if current_total <= previous_total:
                    valid = False
                    break

                previous_total = current_total

            if valid:
                result.append(customer_id)

        return sorted(result)

solution = Solution()

# Provided example
orders = [
    [1, 1, 2019, 1100],
    [2, 1, 2019, 1200],
    [3, 1, 2020, 3000],
    [4, 1, 2021, 3100],
    [5, 1, 2022, 4700],
    [6, 2, 2015, 700],
    [7, 2, 2017, 1000],
    [8, 3, 2017, 900],
    [9, 3, 2018, 900],
]
assert solution.strictlyIncreasingPurchases(orders) == [1]  # official example

# Single customer, strictly increasing
orders = [
    [1, 1, 2020, 100],
    [2, 1, 2021, 200],
    [3, 1, 2022, 300],
]
assert solution.strictlyIncreasingPurchases(orders) == [1]  # simple increasing case

# Missing year causes zero
orders = [
    [1, 1, 2020, 500],
    [2, 1, 2022, 1000],
]
assert solution.strictlyIncreasingPurchases(orders) == []  # 2021 becomes zero

# Equal totals
orders = [
    [1, 1, 2020, 500],
    [2, 1, 2021, 500],
]
assert solution.strictlyIncreasingPurchases(orders) == []  # equal is not strictly increasing

# Decreasing totals
orders = [
    [1, 1, 2020, 700],
    [2, 1, 2021, 600],
]
assert solution.strictlyIncreasingPurchases(orders) == []  # decreasing totals

# Multiple orders same year
orders = [
    [1, 1, 2020, 100],
    [2, 1, 2020, 200],
    [3, 1, 2021, 400],
]
assert solution.strictlyIncreasingPurchases(orders) == [1]  # yearly aggregation

# Single year only
orders = [
    [1, 1, 2020, 500],
]
assert solution.strictlyIncreasingPurchases(orders) == [1]  # vacuously increasing

# Multiple customers
orders = [
    [1, 1, 2020, 100],
    [2, 1, 2021, 200],
    [3, 2, 2020, 300],
    [4, 2, 2021, 200],
]
assert solution.strictlyIncreasingPurchases(orders) == [1]  # mixed validity
Test Why
Official example Validates all major conditions together
Strictly increasing totals Basic success case
Missing year Ensures implicit zero handling
Equal totals Verifies strict inequality
Decreasing totals Ensures invalid decreasing sequences fail
Multiple orders same year Confirms yearly aggregation logic
Single year only Validates minimal range handling
Multiple customers Ensures independent customer evaluation

Edge Cases

Missing Years Between Purchases

A customer may place orders in nonconsecutive years. This is the most important edge case because missing years must count as zero purchases.

For example:

2020 -> 500
2022 -> 1000

must be interpreted as:

2020 -> 500
2021 -> 0
2022 -> 1000

A naive implementation that only compares existing years would incorrectly conclude that 500 < 1000 and mark the customer as valid. The implementation avoids this bug by iterating through every year in the full range.

Equal Consecutive Totals

Strictly increasing means every value must be greater than the previous one. Equality is not allowed.

For example:

2020 -> 900
2021 -> 900

should fail.

The implementation uses:

if current_total <= previous_total:

which correctly rejects both equal and decreasing totals.

Customers With Only One Purchase Year

If a customer only has purchases in one year, there are no adjacent years to compare.

For example:

2020 -> 500

This should be considered valid because there is no violation of the strictly increasing condition.

The implementation handles this naturally because the loop runs once and never encounters a failing comparison.