LeetCode 3401 - Find Circular Gift Exchange Chains

Here’s a full technical solution guide following your requested format for LeetCode 3401 - Find Circular Gift Exchange Chains: This problem asks us to analyze a table of gift exchanges in a Secret Santa setting and identify circular chains of gift exchanges.

leetcodeharddatabase

LeetCode Problem 3401

Difficulty: 🔴 Hard
Topics: Database

Solution

Here’s a full technical solution guide following your requested format for LeetCode 3401 - Find Circular Gift Exchange Chains:

Problem Understanding

This problem asks us to analyze a table of gift exchanges in a Secret Santa setting and identify circular chains of gift exchanges. Each row in the SecretSanta table represents a gift transaction, with giver_id as the person giving the gift, receiver_id as the person receiving the gift, and gift_value representing the value of that gift.

A circular chain is defined as a closed loop where every employee gives a gift to exactly one person and receives a gift from exactly one person, eventually forming a loop. For example, if employee A gives to B, B gives to C, and C gives back to A, this forms a circular chain of length 3. Another example is a pair of employees exchanging gifts with each other, forming a chain of length 2.

The input is a set of giver_id, receiver_id, and gift_value rows. The output is a table listing each circular chain, with columns chain_id (a sequential identifier), chain_length (number of participants in the loop), and total_gift_value (sum of all gift values in the chain). The result must be ordered descending by chain length and total gift value.

The problem guarantees that each giver gives a gift to exactly one person and each receiver receives from exactly one person, which implies the gift exchanges can be modeled as disjoint cycles in a directed graph. Edge cases include very small chains (length 2) or multiple disconnected chains.

Approaches

A brute-force approach would enumerate all possible sequences of employees and check which ones form circular loops. This would involve iterating through permutations and verifying gift exchanges form a cycle. While correct in principle, the approach is infeasible for large datasets because it has factorial time complexity, O(n!) for n employees, and is combinatorially explosive.

The optimal approach leverages the fact that each employee gives and receives exactly one gift. This forms a functional graph, which consists of disjoint cycles. We can traverse the gift exchanges starting from each unvisited employee, following the receiver_id pointer until we return to the starting employee. By keeping track of visited nodes, we avoid revisiting cycles. During traversal, we sum the gift values to compute the total for each chain. Finally, we assign sequential chain IDs and sort by chain length and total gift value in descending order.

Approach Time Complexity Space Complexity Notes
Brute Force O(n!) O(n) Generate all permutations to find cycles; infeasible for large n
Optimal O(n) O(n) Traverse each employee exactly once, summing gift values in cycles

Algorithm Walkthrough

  1. Initialize data structures: Create a mapping from giver_id to (receiver_id, gift_value) for constant-time lookups. Create a set or map to track visited employees.
  2. Iterate over all employees: For each unvisited giver_id, start a traversal to find the circular chain it belongs to.
  3. Traverse the cycle: Initialize a counter for chain_length and a sum for total_gift_value. Starting from the current giver, follow the receiver_id mapping until you return to the starting giver, marking each employee as visited and accumulating gift values.
  4. Record the cycle: After completing the traversal, store the cycle's length and total gift value in a results list.
  5. Assign chain IDs and sort: Once all cycles are discovered, enumerate them with chain_id starting from 1. Sort the results first by chain length descending, then by total gift value descending.
  6. Return results: Format the result as a table with columns chain_id, chain_length, and total_gift_value.

Why it works: The algorithm guarantees each employee is visited exactly once, and since the input forms a functional graph, all traversals will terminate in a cycle. This ensures no cycles are missed, and every gift is counted exactly once per cycle.

Python Solution

from typing import List
import collections

class Solution:
    def findCircularChains(self, secretSanta: List[List[int]]) -> List[List[int]]:
        # Step 1: Build giver -> (receiver, value) map
        giver_map = {giver: (receiver, value) for giver, receiver, value in secretSanta}
        visited = set()
        chains = []

        # Step 2: Traverse each employee
        for giver in giver_map:
            if giver in visited:
                continue

            chain_length = 0
            total_gift_value = 0
            current = giver

            # Step 3: Follow the cycle
            while current not in visited:
                visited.add(current)
                receiver, value = giver_map[current]
                total_gift_value += value
                chain_length += 1
                current = receiver

            chains.append((chain_length, total_gift_value))

        # Step 4: Sort chains
        chains.sort(key=lambda x: (-x[0], -x[1]))

        # Step 5: Assign chain IDs
        result = [[i + 1, length, total] for i, (length, total) in enumerate(chains)]
        return result

This implementation first builds a mapping for efficient traversal. It iterates through each giver, starting a cycle traversal only if the employee has not been visited. During traversal, it accumulates the gift value and counts the chain length. Finally, it sorts and formats the results for output.

Go Solution

package main

type SecretSanta struct {
    GiverID    int
    ReceiverID int
    GiftValue  int
}

func findCircularChains(secretSanta []SecretSanta) [][]int {
    giverMap := make(map[int][2]int)
    visited := make(map[int]bool)
    chains := [][]int{}

    // Step 1: Build giver -> (receiver, value) map
    for _, entry := range secretSanta {
        giverMap[entry.GiverID] = [2]int{entry.ReceiverID, entry.GiftValue}
    }

    // Step 2: Traverse each employee
    for giver := range giverMap {
        if visited[giver] {
            continue
        }

        chainLength := 0
        totalGiftValue := 0
        current := giver

        // Step 3: Follow the cycle
        for !visited[current] {
            visited[current] = true
            receiver := giverMap[current][0]
            value := giverMap[current][1]
            totalGiftValue += value
            chainLength++
            current = receiver
        }

        chains = append(chains, []int{chainLength, totalGiftValue})
    }

    // Step 4: Sort chains
    sort.Slice(chains, func(i, j int) bool {
        if chains[i][0] != chains[j][0] {
            return chains[i][0] > chains[j][0]
        }
        return chains[i][1] > chains[j][1]
    })

    // Step 5: Assign chain IDs
    result := [][]int{}
    for i, chain := range chains {
        result = append(result, []int{i + 1, chain[0], chain[1]})
    }

    return result
}

Go handles maps, slices, and sorting slightly differently than Python. Note the use of [2]int to store (receiver, gift_value) and sort.Slice for multi-key sorting.

Worked Examples

Input:

1 -> 2 (20)
2 -> 3 (30)
3 -> 1 (40)
4 -> 5 (25)
5 -> 4 (35)

Execution steps:

Step Current Visited Chain Length Total Value
1 1 {} 0 0
2 2 {1} 1 20
3 3 {1,2} 2 50
4 1 {1,2,3} 3 90
5 4 {1,2,3} 0 0
6 5 {1,2,3,4} 1 25
7 4 {1,2,3,4,5} 2 60

Sorted by chain length then total value:

[(3, 90), (2, 60)]

Assigned chain IDs:

[[1, 3, 90], [2, 2, 60]]

Problem Understanding

This is a SQL graph problem. Each row in SecretSanta represents a directed edge from giver_id to receiver_id, with an associated edge weight gift_value.

The problem asks us to identify all circular gift exchange chains. A circular chain is exactly a directed cycle in the graph:

  • Every participant in the chain gives a gift to exactly one other participant.
  • Every participant in the chain receives a gift from exactly one other participant.
  • Following the gift exchanges eventually returns to the starting employee.

For every such cycle, we must compute:

  • chain_length, the number of employees in the cycle.
  • total_gift_value, the sum of all gift_value values along the cycle.

The output must assign a sequential chain_id and return all detected cycles ordered by:

  1. chain_length descending.
  2. total_gift_value descending.

The example contains two disconnected cycles:

1 → 2 → 3 → 1

and

4 → 5 → 4

The first cycle has length 3 and total value 90, while the second has length 2 and total value 60.

The key observation is that the table represents a directed graph where each employee participates in at most one outgoing edge. Detecting circular chains therefore becomes a cycle detection problem. The challenge is grouping all members of the same cycle together and computing aggregate statistics for each cycle exactly once.

Important edge cases include cycles of length one (self-loops), multiple disconnected cycles, cycles with identical lengths but different total values, and graphs containing employees that are not part of any cycle. The solution must ensure that only complete circular chains are reported.

Approaches

Brute Force

A naive approach would start from every employee and repeatedly follow gift exchanges until either:

  • a previously visited employee is encountered, or
  • the path terminates.

For every starting employee we would reconstruct the entire traversal path and attempt to determine whether a cycle exists.

This approach is correct because every cycle can eventually be discovered by following outgoing edges. However, the same cycle may be traversed many times from different starting points. If there are $n$ employees, a cycle of length $k$ could be rediscovered $k$ times.

As a result, the total work can grow quadratically.

Key Insight

The gift exchanges form a directed graph. Every circular chain is a strongly connected component consisting entirely of a cycle.

Instead of repeatedly traversing the same nodes, we can perform a recursive graph walk while maintaining:

  • the current traversal path,
  • the position of each node within that path,
  • a global visited set.

When we revisit a node already present in the current traversal stack, we have detected an entire cycle. The cycle members are exactly the nodes from the first occurrence of that node to the current position.

Once a cycle is identified, we can compute:

  • cycle length,
  • total gift value,

and store the result exactly once.

This ensures each edge and node is processed only once.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Repeatedly traverses the same chains from different starting points
Optimal O(n) O(n) Each node and edge is processed once during cycle detection

Algorithm Walkthrough

Optimal SQL Strategy Using Recursive CTE

Since this is a database problem, the intended solution uses recursive traversal.

  1. Start a recursive search from every employee.
  2. Maintain the current path as a string containing all visited employees.
  3. Repeatedly follow the edge from the current employee to its receiver.
  4. Accumulate:
  • current chain length,
  • running gift value sum.
  1. Whenever the traversal returns to the original starting employee, a cycle has been completed.
  2. Record the completed cycle together with its length and total value.
  3. Because every member of a cycle can generate the same cycle, select a canonical representative, typically the minimum employee id in the cycle.
  4. Aggregate results so that each cycle appears exactly once.
  5. Sort by chain length descending and total gift value descending.
  6. Generate sequential chain_id values using ROW_NUMBER().

Why it works

The recursive traversal follows exactly the directed edges defined by the Secret Santa assignments. A cycle is reported only when the walk returns to its starting employee. Selecting a canonical representative eliminates duplicate detections of the same cycle. Therefore every circular chain appears exactly once, and its length and gift value are computed from exactly the edges belonging to that chain.

SQL Solution

WITH RECURSIVE chains AS (
    SELECT
        giver_id AS start_id,
        giver_id AS current_id,
        receiver_id,
        gift_value,
        CAST(giver_id AS CHAR(500)) AS path,
        1 AS chain_length,
        gift_value AS total_gift_value
    FROM SecretSanta

    UNION ALL

    SELECT
        c.start_id,
        s.giver_id,
        s.receiver_id,
        s.gift_value,
        CONCAT(c.path, ',', s.giver_id),
        c.chain_length + 1,
        c.total_gift_value + s.gift_value
    FROM chains c
    JOIN SecretSanta s
        ON c.receiver_id = s.giver_id
    WHERE FIND_IN_SET(s.giver_id, c.path) = 0
),
cycles AS (
    SELECT
        c.start_id,
        c.chain_length,
        c.total_gift_value,
        (
            SELECT MIN(CAST(val AS UNSIGNED))
            FROM (
                SELECT SUBSTRING_INDEX(
                    SUBSTRING_INDEX(c.path, ',', nums.n),
                    ',',
                    -1
                ) AS val
                FROM (
                    SELECT 1 n UNION ALL SELECT 2 UNION ALL SELECT 3
                    UNION ALL SELECT 4 UNION ALL SELECT 5 UNION ALL SELECT 6
                    UNION ALL SELECT 7 UNION ALL SELECT 8 UNION ALL SELECT 9
                    UNION ALL SELECT 10
                ) nums
                WHERE nums.n <=
                    1 + LENGTH(c.path) - LENGTH(REPLACE(c.path, ',', ''))
            ) x
        ) AS canonical_id
    FROM chains c
    WHERE c.receiver_id = c.start_id
),
unique_cycles AS (
    SELECT
        canonical_id,
        MAX(chain_length) AS chain_length,
        MAX(total_gift_value) AS total_gift_value
    FROM cycles
    GROUP BY canonical_id
)
SELECT
    ROW_NUMBER() OVER (
        ORDER BY chain_length DESC,
                 total_gift_value DESC
    ) AS chain_id,
    chain_length,
    total_gift_value
FROM unique_cycles
ORDER BY chain_length DESC,
         total_gift_value DESC;

Implementation Discussion

The recursive CTE named chains performs graph traversal. Each recursive step follows the next gift exchange and extends the path while accumulating both chain length and gift value.

The condition

FIND_IN_SET(s.giver_id, c.path) = 0

prevents revisiting employees already encountered in the current traversal.

A completed cycle is detected when:

c.receiver_id = c.start_id

meaning the next edge returns to the employee where the traversal began.

Since every member of a cycle can serve as a starting point, duplicates naturally occur. The canonical_id calculation chooses the smallest employee id in the cycle, allowing all duplicate discoveries to be grouped together.

The final query assigns sequential chain identifiers using ROW_NUMBER() and applies the required ordering.

Worked Example

Given:

giver_id receiver_id gift_value
1 2 20
2 3 30
3 1 40
4 5 25
5 4 35

Traversal Starting at Employee 1

Step Current Path Length Total Value
Start 1 1 20
Follow 2 1,2 2 50
Follow 3 1,2,3 3 90

The next receiver is employee 1, which is the start node.

Cycle discovered:

1 → 2 → 3 → 1

Statistics:

Measure Value
Length 3
Total Gift Value 90

Traversal Starting at Employee 4

Step Current Path Length Total Value
Start 4 1 25
Follow 5 4,5 2 60

The next receiver is employee 4.

Cycle discovered:

4 → 5 → 4

Statistics:

Measure Value
Length 2
Total Gift Value 60

Final Ordering

chain_id chain_length total_gift_value
1 3 90
2 2 60

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each employee is visited exactly once to form cycles, with constant-time map lookups. Sorting takes O(k log k), where k is number of cycles, usually ≤ n.
Space O(n) Maps store giver -> receiver mapping and visited set; auxiliary space for results list.

The algorithm scales linearly with the number of employees, making it efficient even for large datasets.

Test Cases

# Provided example
assert Solution().findCircularChains([
    [1

| Time | O(n) | Each exchange is traversed a constant number of times during recursive exploration | | Space | O(n) | Path tracking and recursion store at most all employees |

The graph contains one row per gift exchange. The recursive traversal processes each edge only while extending a path. Cycle aggregation and final sorting operate on the set of discovered cycles, which is at most the number of employees.

Test Cases

Although LeetCode Database problems are validated through SQL execution rather than Python, the following logical test cases verify correctness.

# Example from statement
# Cycle: 1->2->3->1 (90)
# Cycle: 4->5->4 (60)

# Single self-loop
# 1->1 value=10
# Expected: length=1, total=10

# Multiple independent cycles
# 1->2->1 value=20+30
# 3->4->5->3 value=10+15+25

# Equal lengths, different totals
# Cycle A length=3 total=100
# Cycle B length=3 total=70
# A must appear before B

# Large cycle containing every employee
# 1->2->3->...->n->1

# Cycle with minimum employee not being start node
# 5->7->2->5
# Canonical representative should still identify one cycle

# Disconnected graph with several cycles
# Ensures duplicate cycle detection is removed

# All employees in self-loops
# 1->1, 2->2, 3->3
# Three separate chains of length 1

Test Summary

Test Why
Problem example Verifies basic cycle aggregation
Self-loop Validates length-one cycle handling
Multiple cycles Ensures disconnected components work
Equal lengths Verifies secondary ordering by gift value
Large cycle Tests maximum cycle size
Non-minimum start node Verifies duplicate elimination logic
Several disconnected cycles Ensures unique reporting
All self-loops Confirms multiple length-one chains

Edge Cases

Self-Loop Cycle

An employee may give a gift to themselves:

1 → 1

This is a valid circular chain of length one. Implementations that assume a cycle must contain at least two employees would incorrectly exclude it. The recursive traversal correctly identifies it because the receiver immediately equals the starting employee.

Duplicate Discovery of the Same Cycle

For the cycle

1 → 2 → 3 → 1

starting from employee 1, 2, or 3 all discovers the same chain. Without canonicalization, the output would contain three copies of the same cycle. The solution assigns a canonical representative and groups duplicates together.

Multiple Cycles with Identical Lengths

Consider:

1 → 2 → 3 → 1

with total value 100, and

4 → 5 → 6 → 4

with total value 70.

Both cycles have length 3. The required ordering then depends on total gift value. The final ORDER BY clause correctly sorts first by length descending and then by total value descending.

Disconnected Components

The graph may contain several independent circular chains. A solution that assumes a single connected structure would miss valid cycles. Starting recursive traversal from every employee guarantees that all components are explored and every circular chain is reported.