Skip to content

3401. Find Circular Gift Exchange Chains 👍

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
WITH RECURSIVE
  Chains AS (
    SELECT *, giver_id AS start_id
    FROM SecretSanta
    UNION ALL
    SELECT SecretSanta.*, Chains.start_id
    FROM SecretSanta
    INNER JOIN Chains
      ON (
        SecretSanta.giver_id = Chains.receiver_id
        AND SecretSanta.giver_id != Chains.start_id) -- Avoid cycles.
  ),
  ChainSummary AS (
    SELECT
      start_id,
      COUNT(*) AS chain_length,
      SUM(gift_value) AS total_gift_value
    FROM Chains
    GROUP BY 1
  ),
  UniqueChains AS (
    SELECT DISTINCT chain_length, total_gift_value
    FROM ChainSummary
  )
SELECT
  RANK() OVER(
    ORDER BY chain_length DESC, total_gift_value DESC
  ) AS chain_id,
  chain_length,
  total_gift_value
FROM UniqueChains;