Maximize Value of Function in a Ball Passing Game

Hard

#2536Time: O(n * k). The outer loop runs `n` times, and for each iteration, the inner loop runs `k` times. Given `n` up to `10^5` and `k` up to `10^10`, this is computationally infeasible.Space: O(1), as we only use a few variables to store the current state, not counting the input array.

Patterns

Dynamic Programming Bit Manipulation

Data structures

Array

Prompt

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 <= 10⁵
0 <= receiver[i] <= n - 1
1 <= k <= 10¹⁰

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the ball-passing game for each possible starting player. We iterate through all n players, considering each one as a potential starting point. For each starting player, we simulate k passes, accumulating the score along the way by adding the index of each player who touches the ball.

Algorithm

Initialize a variable max_score to 0.
Loop through each player i from 0 to n-1 to consider them as the starting player.
For each starting player i, initialize current_score = i and current_player = i.
Loop k times to simulate the passes:
- Update current_player to receiver[current_player].
- Add the new current_player's index to current_score.
After the inner loop, current_score holds the total score for starting with player i. Update max_score = max(max_score, current_score).
After iterating through all possible starting players, max_score will hold the maximum possible score.

Walkthrough

The algorithm iterates through every possible starting player from 0 to n-1. For each start player, it simulates the game for k passes. In each pass, it finds the next player using the receiver array and adds their index to a running total for the current game. This process is repeated k times. The maximum score found across all possible starting players is then returned.

1class Solution {2    public long getMaxFunctionValue(int[] receiver, long k) {3        int n = receiver.length;4        long maxScore = 0;5 6        for (int i = 0; i < n; i++) {7            long currentScore = i;8            int currentPlayer = i;9            for (long j = 0; j < k; j++) {10                currentPlayer = receiver[currentPlayer];11                currentScore += currentPlayer;12            }13            maxScore = Math.max(maxScore, currentScore);14        }15        return maxScore;16    }17}

Complexity

Time

O(n * k). The outer loop runs `n` times, and for each iteration, the inner loop runs `k` times. Given `n` up to `10^5` and `k` up to `10^10`, this is computationally infeasible.

Space

O(1), as we only use a few variables to store the current state, not counting the input array.

Trade-offs

Pros

Simple to understand and implement.
Requires minimal memory.

Cons

Extremely inefficient for large values of k.
Will result in a 'Time Limit Exceeded' (TLE) error on most platforms for the given constraints.

The brute-force approach is too slow because k can be very large. We can optimize this by precomputing information about paths of lengths that are powers of two. This technique is known as binary lifting or sparse table. The core idea is to break down the long path of k passes into segments whose lengths are powers of two. After an O(n log k) precomputation, we can find the destination and the sum of any path of length k in O(log k) time.

Algorithm

Precomputation:
- Determine the maximum power of two needed, m, which is approximately log2(k).
- Create two 2D arrays: nextPlayer[n][m] to store the destination after 2^j steps, and pathSum[n][m] to store the sum of indices over a path of 2^j steps.
- Initialize the base cases for j=0 (path of length 2^0 = 1):
  - nextPlayer[i][0] = receiver[i]
  - pathSum[i][0] = i
- Use dynamic programming to fill the tables for j from 1 to m-1:
  - nextPlayer[i][j] = nextPlayer[nextPlayer[i][j-1]][j-1]
  - pathSum[i][j] = pathSum[i][j-1] + pathSum[nextPlayer[i][j-1]][j-1]
Querying:
- Initialize max_score = 0.
- For each player i from 0 to n-1:
  - Calculate the score for a path of length k+1 (for k passes).
  - Use the binary representation of k+1 to assemble the path from the precomputed segments.
  - Iterate j from m-1 down to 0. If the j-th bit of k+1 is set, add the corresponding pathSum and advance the currentPlayer.
  - Update max_score with the calculated score for starting player i.
Return max_score.

Walkthrough

We use dynamic programming to precompute jumps of powers of two. We create two tables:

nextPlayer[i][j]: stores the player you reach after 2^j passes starting from player i.
pathSum[i][j]: stores the sum of player indices on a path of 2^j nodes, starting from player i.

The recurrence relations are:

nextPlayer[i][j] = nextPlayer[nextPlayer[i][j-1]][j-1] (A jump of 2^j is two jumps of 2^(j-1)).
pathSum[i][j] = pathSum[i][j-1] + pathSum[nextPlayer[i][j-1]][j-1] (The sum for a 2^j path is the sum of the first 2^(j-1) path segment plus the sum of the next 2^(j-1) path segment).

After precomputing these tables, we can answer the query for any starting player i and any number of passes k. The total score is the sum of indices of k+1 players. We find this sum by decomposing k+1 into its binary representation and summing up the precomputed pathSum values for the corresponding powers of two.

1class Solution {2    public long getMaxFunctionValue(int[] receiver, long k) {3        int n = receiver.length;4        // The number of bits needed to represent k. Add 1 for safety.5        int m = (int) (Math.log(k) / Math.log(2)) + 2;6 7        // nextPlayer[i][j]: player after 2^j steps starting from i8        int[][] nextPlayer = new int[n][m];9        // pathSum[i][j]: sum of path of length 2^j starting from i10        long[][] pathSum = new long[n][m];11 12        // Base cases (j=0, i.e., 2^0 = 1 node path)13        for (int i = 0; i < n; i++) {14            nextPlayer[i][0] = receiver[i];15            pathSum[i][0] = i;16        }17 18        // Precomputation using DP19        for (int j = 1; j < m; j++) {20            for (int i = 0; i < n; i++) {21                int prevHalfEndNode = nextPlayer[i][j - 1];22                nextPlayer[i][j] = nextPlayer[prevHalfEndNode][j - 1];23                pathSum[i][j] = pathSum[i][j - 1] + pathSum[prevHalfEndNode][j - 1];24            }25        }26 27        long maxScore = 0;28        // The total number of players in the sum is k+1 (k passes + 1 start player)29        long pathLength = k + 1;30 31        for (int i = 0; i < n; i++) {32            long currentScore = 0;33            int currentPlayer = i;34            long len = pathLength;35 36            for (int j = m - 1; j >= 0; j--) {37                if ((len >> j & 1) == 1) {38                    currentScore += pathSum[currentPlayer][j];39                    currentPlayer = nextPlayer[currentPlayer][j];40                }41            }42            maxScore = Math.max(maxScore, currentScore);43        }44 45        return maxScore;46    }47}

Complexity

Time

O(n * log k). The precomputation takes `O(n * log k)`. The query part iterates through `n` starting nodes, and each query takes `O(log k)`. The total time is dominated by these two parts.

Space

O(n * log k). We use two 2D arrays of size `n x m`, where `m` is approximately `log2(k)`.

Trade-offs

Pros

Highly efficient for large k, making it feasible for the given constraints.
It's a standard and powerful technique for path-related problems on functional graphs or trees.

Cons

Uses significantly more memory, O(n * log k), compared to the brute-force approach.
The implementation is more complex and less intuitive than a direct simulation.

Solutions

Solution

1class Solution {2public3  long getMaxFunctionValue(List<Integer> receiver, long k) {4    int n = receiver.size(), m = 64 - Long.numberOfLeadingZeros(k);5    int[][] f = new int[n][m];6    long[][] g = new long[n][m];7    for (int i = 0; i < n; ++i) {8      f[i][0] = receiver.get(i);9      g[i][0] = i;10    }11    for (int j = 1; j < m; ++j) {12      for (int i = 0; i < n; ++i) {13        f[i][j] = f[f[i][j - 1]][j - 1];14        g[i][j] = g[i][j - 1] + g[f[i][j - 1]][j - 1];15      }16    }17    long ans = 0;18    for (int i = 0; i < n; ++i) {19      int p = i;20      long t = 0;21      for (int j = 0; j < m; ++j) {22        if ((k >> j & 1) == 1) {23          t += g[p][j];24          p = f[p][j];25        }26      }27      ans = Math.max(ans, p + t);28    }29    return ans;30  }31}

1class Solution {2public:3  long long getMaxFunctionValue(vector<int> &receiver, long long k) {4    int n = receiver.size(), m = 64 - __builtin_clzll(k);5    int f[n][m];6    long long g[n][m];7    for (int i = 0; i < n; ++i) {8      f[i][0] = receiver[i];9      g[i][0] = i;10    }11    for (int j = 1; j < m; ++j) {12      for (int i = 0; i < n; ++i) {13        f[i][j] = f[f[i][j - 1]][j - 1];14        g[i][j] = g[i][j - 1] + g[f[i][j - 1]][j - 1];15      }16    }17    long long ans = 0;18    for (int i = 0; i < n; ++i) {19      int p = i;20      long long t = 0;21      for (int j = 0; j < m; ++j) {22        if (k >> j & 1) {23          t += g[p][j];24          p = f[p][j];25        }26      }27      ans = max(ans, p + t);28    }29    return ans;30  }31};

1class Solution:2    def getMaxFunctionValue(self, receiver: List[int], k: int) -> int: n, m = len(receiver), k . bit_length() f = [[0] * m for _ in range(n)] g = [[0] * m for _ in range(n)] for i, x in enumerate(receiver): f[i][0] = x g[i][0] = i for j in range(1, m): for i in range(n): f[i][j] = f[f[i][j - 1]][j - 1] g[i][j] = g[i][j - 1] + g[f[i][j - 1]][j - 1] ans = 0 for i in range(n): p, t = i, 0 for j in range(m): if k >> j & 1: t += g[p][j] p = f[p][j] ans = max(ans, t + p) return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem