Dream11: Longest Run of Matches With the Same Captain
Dream11's personalisation team wants to know how loyal users are to a captain.
- Difficulty: Hard
- Topics: Window Functions, Joins
- Dialect: MySQL
- Problem: #642
Problem statement
Dream11's personalisation team wants to know how loyal users are to a captain. Take each user's saved teams in match order (by the match's start_time, then match_id); a run is a stretch of consecutive teams with the same captain_id.
For every user with at least one team, return user_id and longest_run, the length of their longest run (a user who changed captain every match has 1). Order by longest_run descending, then by user_id.
A practice scenario set at Dream11: the tables and data are invented, and this is not a question from, or endorsed by, Dream11.
Tables
Table: FixtureMatch
| Column | Type |
|---|---|
| match_id | int |
| fixture | varchar |
| start_time | datetime |
Primary key: match_id.
Two matches can start at the same time (double-headers on different grounds).
Table: UserTeam
| Column | Type |
|---|---|
| team_id | int |
| user_id | int |
| match_id | int |
| captain_id | int |
Primary key: team_id.
In this extract a user saves at most one team per match. Matches the user skipped do not break a run.
Examples
Example 1
FixtureMatch
| match_id | fixture | start_time |
|---|---|---|
| 1 | MUM vs CHE | 2025-04-01 19:30:00 |
| 2 | BLR vs KOL | 2025-04-02 19:30:00 |
| 3 | DEL vs HYD | 2025-04-03 15:30:00 |
| 4 | PUN vs RAJ | 2025-04-03 15:30:00 |
| 5 | GUJ vs LKO | 2025-04-04 19:30:00 |
| 6 | MUM vs KOL | 2025-04-05 19:30:00 |
UserTeam
| team_id | user_id | match_id | captain_id |
|---|---|---|---|
| 10 | 71 | 1 | 7 |
| 11 | 71 | 2 | 7 |
| 12 | 71 | 3 | 9 |
| 13 | 71 | 4 | 7 |
| 14 | 71 | 5 | 7 |
| 15 | 71 | 6 | 7 |
| 16 | 72 | 1 | 3 |
| 17 | 72 | 3 | 3 |
| 18 | 72 | 6 | 3 |
| 19 | 73 | 2 | 5 |
| 20 | 73 | 5 | 8 |
Output
| user_id | longest_run |
|---|---|
| 71 | 3 |
| 72 | 3 |
| 73 | 1 |
How to solve Dream11: Longest Run of Matches With the Same Captain
A run is an island: a maximal stretch of consecutive rows, in a given order, that share a value. The classic trick numbers each user's teams twice — rn_all over all their teams in match order, rn_cap over only the teams with the same captain, in the same order. While the captain stays the same, both counters advance by one per team, so rn_all − rn_cap is constant; when the user switches away and later comes back to that captain, rn_all has moved on further than rn_cap, and the difference jumps. Grouping by (user, captain, difference) therefore groups exactly the runs, and COUNT(*) is each run's length. (rn_all is never smaller than rn_cap, so the subtraction never goes negative — worth checking, since MySQL's row numbers are unsigned.)
The order has to be total and identical in both windows: two matches can start at the same time, so match_id breaks the tie. The longest run per user is then a MAX.
The alternative compares each team with the previous one through LAG, writes 1 where a new run starts (including the first team, whose LAG is NULL), and turns the marks into run ids with a running SUM. Both are a couple of sorts per user.
Reference solution (MySQL)
WITH ordered_teams AS (
SELECT t.user_id, t.captain_id,
ROW_NUMBER() OVER (PARTITION BY t.user_id ORDER BY m.start_time, m.match_id) AS rn_all,
ROW_NUMBER() OVER (PARTITION BY t.user_id, t.captain_id ORDER BY m.start_time, m.match_id) AS rn_cap
FROM UserTeam t
JOIN FixtureMatch m ON m.match_id = t.match_id
),
islands AS (
SELECT user_id, captain_id, rn_all - rn_cap AS grp FROM ordered_teams
),
runs AS (
SELECT user_id, captain_id, grp, COUNT(*) AS run_len FROM islands GROUP BY user_id, captain_id, grp
)
SELECT user_id, MAX(run_len) AS longest_run
FROM runs
GROUP BY user_id
ORDER BY longest_run DESC, user_idAnother way
WITH prev AS (
SELECT t.user_id, t.captain_id, m.start_time, m.match_id,
LAG(t.captain_id) OVER (PARTITION BY t.user_id ORDER BY m.start_time, m.match_id) AS prev_cap
FROM UserTeam t JOIN FixtureMatch m ON m.match_id = t.match_id
),
marked AS (
SELECT user_id,
SUM(CASE WHEN prev_cap = captain_id THEN 0 ELSE 1 END)
OVER (PARTITION BY user_id ORDER BY start_time, match_id ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS run_id
FROM prev
)
SELECT user_id, MAX(n) AS longest_run
FROM (SELECT user_id, run_id, COUNT(*) AS n FROM marked GROUP BY user_id, run_id) r
GROUP BY user_id
ORDER BY longest_run DESC, user_id← Dream11: Contest Prizes When Tied Teams Share a Rank · Dream11: Top Three Users by Net Winnings in Each Sport →