Watch 4 video solutions for Maximize Value of Function in a Ball Passing Game, a hard level problem involving Array, Dynamic Programming, Bit Manipulation. This walkthrough by codingMohan has 1,874 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |