Problem

Given a table GiftExchange with columns person_id and gift_to_id, where each row represents a person giving a gift to another person, find all circular gift exchange chains. A circular chain is a sequence of people where each person gives a gift to the next, and the last person gives a gift to the first, with no repeats except the start/end.

Return all such chains as lists of person_ids, sorted in ascending order by the smallest person_id in each chain.

Example 1:

person_id gift_to_id
1 2
2 3
3 1
4 5
5 4

Output:

1
2

[1,2,3]
[4,5]

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.