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 <= 1010This 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.
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.
C#
Time Complexity: O(n + m), where m is the length of the cycle; optimized unlike standard simulations. Space Complexity: O(n) for index tracking.
| 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. |
The unfair way I got good at Leetcode • Dave Burji • 596,394 views views
Watch 9 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