You are given an integer array receiver of length n and an integer k. n players are playing a ball-passing game.
You choose the starting player, i. The game proceeds as follows: player i passes the ball to player receiver[i], who then passes it to receiver[receiver[i]], and so on, for k passes in total. The game's score is the sum of the indices of the players who touched the ball, including repetitions, i.e. i + receiver[i] + receiver[receiver[i]] + ... + receiver(k)[i].
Return the maximum possible score.
Notes:
receiver may contain duplicates.receiver[i] may be equal to i.
Example 1:
Input: receiver = [2,0,1], k = 4
Output: 6
Explanation:
Starting with player i = 2 the initial score is 2:
| Pass | Sender Index | Receiver Index | Score |
|---|---|---|---|
| 1 | 2 | 1 | 3 |
| 2 | 1 | 0 | 3 |
| 3 | 0 | 2 | 5 |
| 4 | 2 | 1 | 6 |
Example 2:
Input: receiver = [1,1,1,2,3], k = 3
Output: 10
Explanation:
Starting with player i = 4 the initial score is 4:
| Pass | Sender Index | Receiver Index | Score |
|---|---|---|---|
| 1 | 4 | 3 | 7 |
| 2 | 3 | 2 | 9 |
| 3 | 2 | 1 | 10 |
Constraints:
1 <= receiver.length == n <= 1050 <= receiver[i] <= n - 11 <= k <= 1010Problem Overview: You are given an array receiver where receiver[i] tells which player receives the ball from player i. Starting from a player x, the ball is passed exactly k times. The value of the function is the sum of every player index visited during the process. Your goal is to choose the starting player that maximizes this value.
Approach 1: Brute Force Simulation (Time: O(n * k), Space: O(1))
The direct strategy is to try every possible starting player and simulate the ball passing process for exactly k steps. For each step, follow receiver[current] and accumulate the visited player indices into a running sum. After simulating all k passes, track the maximum value across all starting players. This approach uses simple array traversal and no extra data structures. The downside is scalability: when k becomes very large (up to billions), iterating step-by-step becomes computationally infeasible.
Approach 2: Optimized Cycle Detection / Binary Lifting (Time: O(n log k), Space: O(n log k))
The passing structure forms a directed graph where each node has exactly one outgoing edge. Repeated passes eventually fall into cycles. Instead of simulating each pass, precompute jumps using a doubling technique similar to binary lifting. Build two tables: one storing the node reached after 2^j passes and another storing the cumulative sum collected during those passes. Using dynamic programming with bit manipulation, decompose k into powers of two and combine precomputed transitions. This allows jumping large distances in the passing chain while accumulating the correct score. For each starting player, iterate through the bits of k, update the current node using the lifting table, and add the stored sums. The maximum across all starting players is the answer.
Recommended for interviews: The brute force approach demonstrates understanding of the passing process but fails for large k. Interviewers expect the optimized binary lifting technique because it reduces repeated work and handles extremely large pass counts efficiently. Recognizing the functional graph structure and applying doubling is the key insight.
This approach involves simulating the ball-passing game starting from each player and computing the sum of the indices visited for the given k passes. We keep track of the maximum score encountered.
This approach involves iterating over all players and tracking the ball passes. A brute-force simulation can be optimized if k is large by early terminating if a cycle is detected, where cycles can be detected using a set to store visited indices.
This Python function simulates the ball-passing game for each player and calculates the score by tracking the index sum. It checks for cycles by using a dictionary to store visited indices and their positions in the sequence. When a cycle is detected, it calculates how many complete cycles can fit in the remaining passes and adds the cycle's contribution to the score.
Python
JavaScript
Time Complexity: O(n*k) in the worst case with optimizations to reduce checks on repeated cycles. Space Complexity: O(n) for the tracking sets.
This approach optimizes on the first one by leveraging cycle detection in the player index sequence earlier. Once a cycle is found, we calculate how many times it can fit within the remaining steps, allowing for greater efficiency.
We iterate starting from each player and calculate the sequence of ball-passes until either all k passes are made or a cycle is detected. Upon detecting a cycle, we compute its contribution to the score based on how many more complete cycles can fit in the game using the remaining steps.
This C++ function maximizes the score by detecting cycles in the index sequence using an unordered_map. If a cycle is found, we calculate its effect over the remaining passes, fitting as many cycles as possible efficiently to enhance performance.
Time Complexity: O(n + m), where m is the length of the cycle; optimized unlike standard simulations. Space Complexity: O(n) for index tracking.
The problem asks us to find the maximum sum of the player IDs who have touched the ball within k passes starting from each player i. If we solve it by brute force, we need to traverse upwards k times starting from i, with a time complexity of O(k), which will obviously time out.
We can use dynamic programming combined with binary lifting to handle this.
We define f[i][j] as the player ID that can be reached by passing the ball 2^j times starting from player i, and define g[i][j] as the sum of the player IDs that can be reached by passing the ball 2^j times starting from player i (excluding the last player).
When j=0, the number of passes is 1, so f[i][0] = receiver[i], and g[i][0] = i.
When j > 0, the number of passes is 2^j, which is equivalent to passing the ball 2^{j-1} times starting from player i, and then passing the ball 2^{j-1} times starting from player f[i][j-1], so f[i][j] = f[f[i][j-1]][j-1], and g[i][j] = g[i][j-1] + g[f[i][j-1]][j-1].
Next, we can enumerate each player i as the starting player, then accumulate upwards according to the binary representation of k, and finally get the maximum sum of the player IDs who have touched the ball within k passes starting from player i.
The time complexity is O(n times log k), and the space complexity is O(n times log k). Here, n is the number of players.
Similar problems:
| Approach | Complexity |
|---|---|
| Brute Force Simulation | Time Complexity: O(n*k) in the worst case with optimizations to reduce checks on repeated cycles. Space Complexity: O(n) for the tracking sets. |
| Optimized Cycle Detection | Time Complexity: O(n + m), where m is the length of the cycle; optimized unlike standard simulations. Space Complexity: O(n) for index tracking. |
| Dynamic Programming + Binary Lifting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(n * k) | O(1) | Useful for understanding the passing mechanics or when k is very small. |
| Cycle Detection / Binary Lifting | O(n log k) | O(n log k) | Best for large k (up to 1e10). Efficiently jumps multiple passes using doubling. |
2836. Maximize Value of Function in a Ball Passing Game | Binary Lifting | Weekly Leetcode 360 • codingMohan • 1,874 views views
Watch 3 more video solutions →Practice Maximize Value of Function in a Ball Passing Game with our built-in code editor and test cases.
Practice on FleetCode