LeetCode 2752 - Customers with Maximum Number of Transactions on Consecutive Days
The problem gives us a database table named Transactions. Each row represents a transaction made by a customer on a specific date.
Difficulty: 🔴 Hard
Topics: Database
Solution
Problem Understanding
The problem gives us a database table named Transactions. Each row represents a transaction made by a customer on a specific date. The important detail is that the pair (customer_id, transaction_date) is guaranteed to be unique, which means a customer can make at most one transaction per day.
We need to determine which customers achieved the maximum number of consecutive transaction days. A consecutive transaction streak means the customer made transactions on back-to-back calendar days without gaps.
For example, if a customer has transactions on:
2023-05-012023-05-022023-05-03
then their consecutive streak length is 3.
If another customer has transactions on:
2023-05-012023-05-032023-05-04
then the longest consecutive streak is only 2, because 2023-05-03 and 2023-05-04 are consecutive, but 2023-05-01 is separated by a gap.
The final result should contain all customers whose longest streak equals the global maximum streak among all customers.
The output must be sorted by customer_id in ascending order.
Since this is a database problem, the intended solution is written in SQL. The main challenge is grouping dates into consecutive sequences efficiently.
A few important observations and edge cases are worth identifying early:
- A customer may have only one transaction, which forms a streak of length
1. - Multiple customers may tie for the maximum streak length.
- Transactions are not guaranteed to appear in chronological order, so sorting is required.
- Different customers must be processed independently.
- Consecutive means exactly one day apart, not merely close in time.
The uniqueness guarantee on (customer_id, transaction_date) simplifies the problem because we never need to handle duplicate dates for the same customer.
Approaches
Brute Force Approach
A straightforward approach is to process each customer independently, sort all their transaction dates, and then scan the dates to compute the longest consecutive streak.
For every customer:
- Collect all transaction dates.
- Sort them chronologically.
- Compare adjacent dates.
- If the difference is exactly one day, extend the current streak.
- Otherwise, reset the streak counter.
- Keep track of the maximum streak for that customer.
After processing every customer, determine the global maximum streak and return all customers who achieved it.
This approach is logically correct because every possible consecutive sequence is examined directly. However, implementing this naively in SQL can become cumbersome and inefficient, especially if repeated self joins or iterative logic are used.
Optimal Approach
The key insight is that consecutive dates can be transformed into groups using window functions.
Suppose we assign a row number to each transaction date within a customer:
| Date | Row Number |
|---|---|
| 2023-05-01 | 1 |
| 2023-05-02 | 2 |
| 2023-05-03 | 3 |
Now subtract the row number from the date:
| Date | Row Number | Date - Row Number |
|---|---|---|
| 2023-05-01 | 1 | 2023-04-30 |
| 2023-05-02 | 2 | 2023-04-30 |
| 2023-05-03 | 3 | 2023-04-30 |
Notice that all consecutive dates produce the same shifted value.
This means we can group consecutive transaction days using:
transaction_date - INTERVAL row_number DAY
Every consecutive streak collapses into a single grouping key.
Once grouped, we simply count the size of each streak, compute the maximum streak per customer, then compute the global maximum.
This avoids expensive iterative logic and uses efficient SQL window functions.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(N log N) | O(N) | Sort dates for every customer and scan sequentially |
| Optimal | O(N log N) | O(N) | Uses window functions and grouping to identify consecutive streaks efficiently |
Algorithm Walkthrough
- First, partition the transactions by
customer_idand sort each customer's transactions bytransaction_date.
We need chronological ordering because consecutive streaks depend entirely on date order. 2. Assign a row number to each transaction within its customer partition.
We use:
ROW_NUMBER() OVER (
PARTITION BY customer_id
ORDER BY transaction_date
)
This gives every transaction a sequential index. 3. Create a grouping key using the date minus the row number.
For consecutive dates, the difference remains constant.
Example:
| Date | Row Number | Shifted Key |
|---|---|---|
| 2023-05-01 | 1 | 2023-04-30 |
| 2023-05-02 | 2 | 2023-04-30 |
| 2023-05-03 | 3 | 2023-04-30 |
A gap changes the shifted key, naturally splitting streaks.
4. Group by (customer_id, shifted_key).
Every group now represents one consecutive streak. 5. Count the number of rows in each group.
This gives the streak length. 6. For each customer, compute their maximum streak.
A customer may have multiple streaks, so we only care about the longest one.
7. Find the global maximum streak across all customers.
8. Return every customer whose maximum streak equals the global maximum.
9. Sort the result by customer_id.
Why it works
The correctness comes from the invariant that consecutive dates increase by exactly one day while row numbers also increase by exactly one. Their difference therefore remains constant throughout a consecutive sequence.
Whenever a gap occurs, the date increases by more than one day while the row number increases by exactly one, causing the difference to change. This naturally separates different streaks into different groups.
Because every streak forms exactly one group and every group corresponds to exactly one streak, counting group sizes correctly computes streak lengths.
Python Solution
Although the actual LeetCode problem expects SQL, the following Python implementation demonstrates the same algorithmic idea clearly.
from collections import defaultdict
from datetime import timedelta
from typing import List
class Solution:
def customersWithMaxConsecutiveTransactions(
self,
transactions: List[List]
) -> List[int]:
customer_dates = defaultdict(list)
for _, customer_id, transaction_date, _ in transactions:
customer_dates[customer_id].append(transaction_date)
customer_best = {}
global_best = 0
for customer_id, dates in customer_dates.items():
dates.sort()
current_streak = 1
best_streak = 1
for i in range(1, len(dates)):
if dates[i] == dates[i - 1] + timedelta(days=1):
current_streak += 1
else:
current_streak = 1
best_streak = max(best_streak, current_streak)
customer_best[customer_id] = best_streak
global_best = max(global_best, best_streak)
result = []
for customer_id, streak in customer_best.items():
if streak == global_best:
result.append(customer_id)
return sorted(result)
The implementation begins by grouping all transaction dates by customer using a hash map.
Each customer's dates are sorted chronologically because consecutive comparisons only make sense in order.
The algorithm then scans adjacent dates. If the current date is exactly one day after the previous date, the streak continues. Otherwise, the streak resets to 1.
For every customer, we store their longest streak. While doing this, we also maintain the overall global maximum streak.
Finally, we collect all customers whose best streak equals the global maximum and return them in sorted order.
Go Solution
package main
import (
"sort"
"time"
)
type Transaction struct {
TransactionID int
CustomerID int
TransactionDate time.Time
Amount int
}
func customersWithMaxConsecutiveTransactions(
transactions []Transaction,
) []int {
customerDates := make(map[int][]time.Time)
for _, transaction := range transactions {
customerDates[transaction.CustomerID] = append(
customerDates[transaction.CustomerID],
transaction.TransactionDate,
)
}
customerBest := make(map[int]int)
globalBest := 0
for customerID, dates := range customerDates {
sort.Slice(dates, func(i, j int) bool {
return dates[i].Before(dates[j])
})
currentStreak := 1
bestStreak := 1
for i := 1; i < len(dates); i++ {
diff := dates[i].Sub(dates[i-1]).Hours() / 24
if diff == 1 {
currentStreak++
} else {
currentStreak = 1
}
if currentStreak > bestStreak {
bestStreak = currentStreak
}
}
customerBest[customerID] = bestStreak
if bestStreak > globalBest {
globalBest = bestStreak
}
}
var result []int
for customerID, streak := range customerBest {
if streak == globalBest {
result = append(result, customerID)
}
}
sort.Ints(result)
return result
}
The Go implementation follows the same logic as the Python version. One notable difference is that Go requires explicit sorting with sort.Slice.
Date arithmetic is handled using the time package. The difference between dates is computed with Sub() and converted into days using Hours() / 24.
Go maps return zero values automatically, which simplifies frequency tracking and streak storage.
Worked Examples
Example 1
Input:
| transaction_id | customer_id | transaction_date |
|---|---|---|
| 1 | 101 | 2023-05-01 |
| 2 | 101 | 2023-05-02 |
| 3 | 101 | 2023-05-03 |
| 4 | 102 | 2023-05-01 |
| 5 | 102 | 2023-05-03 |
| 6 | 102 | 2023-05-04 |
| 7 | 105 | 2023-05-01 |
| 8 | 105 | 2023-05-02 |
| 9 | 105 | 2023-05-03 |
Customer 101
Sorted dates:
| Index | Date |
|---|---|
| 0 | 2023-05-01 |
| 1 | 2023-05-02 |
| 2 | 2023-05-03 |
Processing:
| Previous | Current | Consecutive | Current Streak | Best |
|---|---|---|---|---|
| 2023-05-01 | 2023-05-02 | Yes | 2 | 2 |
| 2023-05-02 | 2023-05-03 | Yes | 3 | 3 |
Longest streak = 3
Customer 102
Sorted dates:
| Index | Date |
|---|---|
| 0 | 2023-05-01 |
| 1 | 2023-05-03 |
| 2 | 2023-05-04 |
Processing:
| Previous | Current | Consecutive | Current Streak | Best |
|---|---|---|---|---|
| 2023-05-01 | 2023-05-03 | No | 1 | 1 |
| 2023-05-03 | 2023-05-04 | Yes | 2 | 2 |
Longest streak = 2
Customer 105
Sorted dates:
| Index | Date |
|---|---|
| 0 | 2023-05-01 |
| 1 | 2023-05-02 |
| 2 | 2023-05-03 |
Processing:
| Previous | Current | Consecutive | Current Streak | Best |
|---|---|---|---|---|
| 2023-05-01 | 2023-05-02 | Yes | 2 | 2 |
| 2023-05-02 | 2023-05-03 | Yes | 3 | 3 |
Longest streak = 3
Global maximum streak = 3
Final result:
| customer_id |
|---|
| 101 |
| 105 |
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(N log N) | Sorting transaction dates dominates the runtime |
| Space | O(N) | Hash maps and grouped transaction storage require linear space |
The dominant cost comes from sorting transaction dates for each customer. Across all customers, the total number of transactions is N, giving an overall complexity of O(N log N) in the worst case.
The auxiliary storage includes grouped transaction lists and streak tracking structures, both proportional to the number of transactions and customers.
Test Cases
from datetime import date
solution = Solution()
# Example case with two winners
transactions1 = [
[1, 101, date(2023, 5, 1), 100],
[2, 101, date(2023, 5, 2), 150],
[3, 101, date(2023, 5, 3), 200],
[4, 102, date(2023, 5, 1), 50],
[5, 102, date(2023, 5, 3), 100],
[6, 102, date(2023, 5, 4), 200],
[7, 105, date(2023, 5, 1), 100],
[8, 105, date(2023, 5, 2), 150],
[9, 105, date(2023, 5, 3), 200],
]
assert solution.customersWithMaxConsecutiveTransactions(transactions1) == [101, 105]
# Single customer with one transaction
transactions2 = [
[1, 1, date(2023, 1, 1), 100]
]
assert solution.customersWithMaxConsecutiveTransactions(transactions2) == [1]
# Multiple customers all tied with streak 1
transactions3 = [
[1, 1, date(2023, 1, 1), 100],
[2, 2, date(2023, 1, 3), 200],
[3, 3, date(2023, 1, 5), 300],
]
assert solution.customersWithMaxConsecutiveTransactions(transactions3) == [1, 2, 3]
# One customer has longer streak later in timeline
transactions4 = [
[1, 1, date(2023, 1, 1), 100],
[2, 1, date(2023, 1, 5), 100],
[3, 1, date(2023, 1, 6), 100],
[4, 1, date(2023, 1, 7), 100],
]
assert solution.customersWithMaxConsecutiveTransactions(transactions4) == [1]
# Unsorted input transactions
transactions5 = [
[1, 2, date(2023, 1, 3), 100],
[2, 2, date(2023, 1, 1), 100],
[3, 2, date(2023, 1, 2), 100],
]
assert solution.customersWithMaxConsecutiveTransactions(transactions5) == [2]
# Two customers with different streak lengths
transactions6 = [
[1, 1, date(2023, 1, 1), 100],
[2, 1, date(2023, 1, 2), 100],
[3, 2, date(2023, 1, 1), 100],
]
assert solution.customersWithMaxConsecutiveTransactions(transactions6) == [1]
| Test | Why |
|---|---|
| Example input | Verifies the main problem scenario |
| Single transaction | Ensures streak length 1 is handled correctly |
| All streaks length 1 | Confirms ties are returned properly |
| Later longer streak | Verifies maximum streak selection |
| Unsorted input | Ensures sorting logic works |
| Different streak lengths | Confirms correct winner selection |
Edge Cases
One important edge case occurs when every customer has only isolated transaction dates with no consecutive days. In this situation, every customer's maximum streak is 1. A buggy implementation might incorrectly return only one customer instead of all tied customers. The implementation handles this by computing the global maximum first and then collecting every customer whose streak equals that maximum.
Another important case is unsorted transaction input. Database rows and input arrays are not guaranteed to appear chronologically. Without sorting, adjacent comparisons would produce incorrect streak calculations. The implementation explicitly sorts each customer's dates before scanning them.
A third edge case involves customers with multiple separate streaks. For example:
2023-01-01
2023-01-02
2023-01-10
2023-01-11
2023-01-12
The customer has streaks of lengths 2 and 3. The implementation correctly resets the current streak whenever a gap occurs while preserving the largest streak seen so far.
Another subtle edge case is having only one transaction for a customer. Since the loop comparing adjacent dates never executes, the implementation initializes both current_streak and best_streak to 1, ensuring the correct result without requiring special handling.