Scale Engineer

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 ProgrammingBit 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 <= 105
  • 0 <= receiver[i] <= n - 1
  • 1 <= k <= 1010

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.

class Solution {    public long getMaxFunctionValue(int[] receiver, long k) {        int n = receiver.length;        long maxScore = 0;         for (int i = 0; i < n; i++) {            long currentScore = i;            int currentPlayer = i;            for (long j = 0; j < k; j++) {                currentPlayer = receiver[currentPlayer];                currentScore += currentPlayer;            }            maxScore = Math.max(maxScore, currentScore);        }        return maxScore;    }}

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.

Solutions

class Solution {public  long getMaxFunctionValue(List<Integer> receiver, long k) {    int n = receiver.size(), m = 64 - Long.numberOfLeadingZeros(k);    int[][] f = new int[n][m];    long[][] g = new long[n][m];    for (int i = 0; i < n; ++i) {      f[i][0] = receiver.get(i);      g[i][0] = i;    }    for (int j = 1; j < m; ++j) {      for (int i = 0; i < n; ++i) {        f[i][j] = f[f[i][j - 1]][j - 1];        g[i][j] = g[i][j - 1] + g[f[i][j - 1]][j - 1];      }    }    long ans = 0;    for (int i = 0; i < n; ++i) {      int p = i;      long t = 0;      for (int j = 0; j < m; ++j) {        if ((k >> j & 1) == 1) {          t += g[p][j];          p = f[p][j];        }      }      ans = Math.max(ans, p + t);    }    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 →

Next problem