LeetCode 2836 - Maximize Value of Function in a Ball Passing Game
This problem presents a ball-passing game among n players, represented by an array receiver of length n. Each element receiver[i] indicates which player receives the ball when player i passes it. The game starts by selecting a player i as the first to hold the ball.
Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Bit Manipulation
Solution
Problem Understanding
This problem presents a ball-passing game among n players, represented by an array receiver of length n. Each element receiver[i] indicates which player receives the ball when player i passes it. The game starts by selecting a player i as the first to hold the ball. The ball is then passed k times according to the mapping in receiver. The score of a game is calculated as the sum of the indices of the players who touched the ball during all passes, including the starting player. The goal is to determine the maximum possible score across all possible starting players.
The input array may contain duplicate values, meaning multiple players can pass to the same next player, and it may contain self-loops, where a player passes the ball to themselves. The constraints are significant: n can go up to 10^5, but k can go up to 10^10. This rules out any brute-force simulation of k passes, as iterating directly for 10^10 passes is computationally infeasible. Key edge cases include cycles, self-loops, very large k values, and arrays where all players pass to the same next player.
Approaches
Brute Force Approach
A brute-force solution would simulate the ball-passing game starting from each player. For each player, we would sum the indices for k passes. While this approach is straightforward and would yield the correct result, it has a time complexity of O(n * k). Given the constraints, with k up to 10^10, this is infeasible.
Optimal Approach
The key observation is that the ball-passing process eventually forms a cycle. Once we detect a cycle, we can compute the sum of indices in the cycle and then calculate how many complete cycles fit into the remaining passes. We can then add the sum of indices for any leftover passes outside full cycles. This transforms the problem into a mix of cycle detection and arithmetic on sequences rather than full simulation.
We can further optimize by using a visited map or array to detect when we enter a cycle, track the sum up to the cycle, the sum within the cycle, and the cycle length. Once a cycle is detected, we can compute the total contribution of the cycle to the score in constant time by multiplying the cycle sum by the number of full cycles.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n * k) | O(n) | Simulate each starting player for k passes, infeasible for large k |
| Optimal | O(n) | O(n) | Detect cycles and compute contributions mathematically, avoids iterating k times |
Algorithm Walkthrough
- Initialize a variable
max_scoreto store the maximum score found so far. - Iterate through each player
ias a potential starting player. - For each starting player, maintain a
visiteddictionary mapping player index to the pass count when it was first visited. This helps detect cycles. - Track the cumulative sum
scoreas we simulate passing the ball, as well as the sequence of visited indices in order. - Start passing the ball from player
i. For each pass:
a. If the current player has been visited before, a cycle is detected.
b. Record the index where the cycle starts, the length of the cycle, and the sum of indices in the cycle.
c. Compute the number of full cycles that can fit in the remaining passes k and calculate their contribution to the score.
d. Add contributions of any leftover passes after full cycles.
6. If no cycle is detected within k passes, sum the indices directly.
7. Update max_score with the maximum of its current value and the score computed for this starting player.
8. Return max_score.
Why it works: The algorithm works because every ball-passing sequence either reaches a cycle or stops before reaching k passes. By detecting cycles and using arithmetic to compute their contributions instead of iterating through each pass, we can handle very large k efficiently. The visited map ensures that we detect cycles without redundant computation.
Python Solution
from typing import List
class Solution:
def getMaxFunctionValue(self, receiver: List[int], k: int) -> int:
n = len(receiver)
max_score = 0
for start in range(n):
visited = {}
sequence = []
current = start
score = 0
steps = 0
while steps < k:
if current in visited:
cycle_start = visited[current]
cycle_sum = sum(sequence[cycle_start:])
cycle_length = len(sequence) - cycle_start
remaining = k - steps
full_cycles = remaining // cycle_length
leftover = remaining % cycle_length
score += cycle_sum * full_cycles + sum(sequence[cycle_start:cycle_start+leftover])
break
visited[current] = len(sequence)
sequence.append(current)
score += current
current = receiver[current]
steps += 1
max_score = max(max_score, score)
return max_score
The implementation iterates over each player as a starting point, tracks visited players to detect cycles, and calculates contributions efficiently using the cycle's sum and length. This avoids direct iteration over very large k.
Go Solution
func getMaxFunctionValue(receiver []int, k int64) int64 {
n := len(receiver)
var maxScore int64 = 0
for start := 0; start < n; start++ {
visited := make(map[int]int64)
var sequence []int64
current := int64(start)
var score int64 = 0
var steps int64 = 0
for steps < k {
if pos, ok := visited[int(current)]; ok {
cycleStart := pos
var cycleSum int64 = 0
for i := cycleStart; i < int64(len(sequence)); i++ {
cycleSum += sequence[i]
}
cycleLength := int64(len(sequence)) - cycleStart
remaining := k - steps
fullCycles := remaining / cycleLength
leftover := remaining % cycleLength
score += cycleSum*fullCycles + sumSlice(sequence[cycleStart:cycleStart+leftover])
break
}
visited[int(current)] = int64(len(sequence))
sequence = append(sequence, current)
score += current
current = int64(receiver[current])
steps++
}
if score > maxScore {
maxScore = score
}
}
return maxScore
}
func sumSlice(arr []int64) int64 {
var s int64 = 0
for _, v := range arr {
s += v
}
return s
}
The Go version closely mirrors the Python logic. A helper function sumSlice is used to sum a slice of int64 values for cycle contributions. Go requires explicit type conversions between int and int64 to handle large k.
Worked Examples
Example 1: receiver = [2,0,1], k = 4
Starting from player 2:
| Step | Current | Score | Sequence |
|---|---|---|---|
| 0 | 2 | 2 | [2] |
| 1 | 1 | 3 | [2,1] |
| 2 | 0 | 3 | [2,1,0] |
| 3 | 2 | 6 | [2,1,0] → cycle detected |
Maximum score = 6
Example 2: receiver = [1,1,1,2,3], k = 3
Starting from player 4:
| Step | Current | Score | Sequence |
|---|---|---|---|
| 0 | 4 | 4 | [4] |
| 1 | 3 | 7 | [4,3] |
| 2 | 2 | 9 | [4,3,2] |
| 3 | 1 | 10 | [4,3,2,1] |
Maximum score = 10
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Each player is visited at most once per cycle detection; cycle arithmetic is constant time |
| Space | O(n) | Visited map and sequence list can store up to n elements |
The key improvement comes from avoiding iteration over k passes and leveraging cycles in the ball-passing sequences.
Test Cases
# provided examples
assert Solution().getMaxFunctionValue([2,0,1], 4) == 6 # example 1
assert Solution().getMaxFunctionValue([1,1,1,2,3], 3) == 10 # example 2
# edge cases
assert Solution().getMaxFunctionValue([0], 1) == 0 # single player, self-loop
assert Solution().getMaxFunctionValue([0], 10**10) == 0 # large k, single self-loop
assert Solution().getMaxFunctionValue([1,2,3,4,0], 10) == 20 # full cycle sum
assert Solution().getMaxFunctionValue([1,0], 5) == 6 # small cycle repeated
| Test | Why |
|---|---|
| [2,0,1], k=4 |