Problem

Table: SecretSanta

1
2
3
4
5
6
7
8
9

+-------------+------+
| Column Name | Type |
+-------------+------+
| giver_id    | int  |
| receiver_id | int  |
| gift_value  | int  |
+-------------+------+
(giver_id, receiver_id) is the unique key for this table.   
Each row represents a record of a gift exchange between two employees, giver_id represents the employee who gives a gift, receiver_id represents the employee who receives the gift and gift_value represents the value of the gift given.

Write a solution to find the total gift value and length of circular chains of Secret Santa gift exchanges:

A circular chain is defined as a series of exchanges where:

  • Each employee gives a gift to exactly one other employee.
  • Each employee receives a gift from exactly one other employee.
  • The exchanges form a continuous loop (e.g., employee A gives a gift to B, B gives to C, and C gives back to A).

Return the result ordered by the chain length and total gift value of the chain in descending order. 

The result format is in the following example.

Examples

Example 1:

 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

Input:

SecretSanta table:

+----------+-------------+------------+
| giver_id | receiver_id | gift_value |
+----------+-------------+------------+
| 1        | 2           | 20         |
| 2        | 3           | 30         |
| 3        | 1           | 40         |
| 4        | 5           | 25         |
| 5        | 4           | 35         |
+----------+-------------+------------+
Output:

+----------+--------------+------------------+
| chain_id | chain_length | total_gift_value |
+----------+--------------+------------------+
| 1        | 3            | 90               |
| 2        | 2            | 60               |
+----------+--------------+------------------+
Explanation:

Chain 1 involves employees 1, 2, and 3:
Employee 1 gives a gift to 2, employee 2 gives a gift to 3, and employee 3 gives a gift to 1.
Total gift value for this chain = 20 + 30 + 40 = 90.
Chain 2 involves employees 4 and 5:
Employee 4 gives a gift to 5, and employee 5 gives a gift to 4.
Total gift value for this chain = 25 + 35 = 60.
The result table is ordered by the chain length and total gift value of the chain in descending order.

Solution

Method 1 – Cycle Detection with Recursive CTE (SQL) and Graph Traversal (Pandas)

Intuition

A circular gift exchange is a cycle in a directed graph where each node (person) points to another node (gift recipient). We need to find all such cycles.

Approach

  • For SQL (MySQL/PostgreSQL):
    1. Use a recursive CTE to traverse the gift chains starting from each person.
    2. Track the path and stop when a cycle is detected (the path returns to the start).
    3. Only output cycles where the start is the smallest id in the cycle to avoid duplicates.
  • For Python (Pandas):
    1. Build a directed graph from the DataFrame.
    2. Use DFS to find all cycles, keeping track of visited nodes and paths.
    3. Normalize cycles to start from the smallest id and avoid duplicates.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

WITH RECURSIVE chains AS (
  SELECT person_id, gift_to_id, CONCAT(person_id, ',', gift_to_id) AS path, person_id AS start, gift_to_id AS curr, 1 AS len
  FROM GiftExchange
  UNION ALL
  SELECT c.person_id, g.gift_to_id, CONCAT(c.path, ',', g.gift_to_id), c.start, g.gift_to_id, c.len + 1
  FROM chains c
  JOIN GiftExchange g ON c.curr = g.person_id
  WHERE FIND_IN_SET(g.gift_to_id, c.path) = 0 OR (g.gift_to_id = c.start AND c.len > 1)
)
SELECT DISTINCT
  SUBSTRING_INDEX(SUBSTRING_INDEX(path, CONCAT(',', start), -1), CONCAT(',', start), 1) AS chain
FROM chains
WHERE curr = start AND len > 1
ORDER BY chain;
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

WITH RECURSIVE chains AS (
  SELECT person_id, gift_to_id, ARRAY[person_id, gift_to_id] AS path, person_id AS start, gift_to_id AS curr, 1 AS len
  FROM GiftExchange
  UNION ALL
  SELECT c.person_id, g.gift_to_id, path || g.gift_to_id, c.start, g.gift_to_id, c.len + 1
  FROM chains c
  JOIN GiftExchange g ON c.curr = g.person_id
  WHERE NOT g.gift_to_id = ANY(path) OR (g.gift_to_id = c.start AND c.len > 1)
)
SELECT DISTINCT path
FROM chains
WHERE curr = start AND len > 1
ORDER BY path;
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def find_circular_gift_chains(self, df):
        from collections import defaultdict
        graph = defaultdict(list)
        for a, b in zip(df['person_id'], df['gift_to_id']):
            graph[a].append(b)
        res = set()
        def dfs(start, node, path, visited):
            for nei in graph[node]:
                if nei == start and len(path) > 1:
                    cycle = tuple(sorted(path))
                    res.add(cycle)
                elif nei not in visited:
                    dfs(start, nei, path + [nei], visited | {nei})
        for node in graph:
            dfs(node, node, [node], {node})
        return [list(c) for c in sorted(res)]

Complexity

  • ⏰ Time complexity: O(n^2), as each node may be visited in multiple paths for cycle detection.
  • 🧺 Space complexity: O(n^2), for storing paths and cycles.