Rotate Function Solution in Java

Explore More Solutions:

Code Solution


class Solution {
  public int maxRotateFunction(int[] nums) {
    final int sum = Arrays.stream(nums).sum();
    int f = 0;

    // Calculate F(0) first.
    for (int i = 0; i < nums.length; ++i)
      f += i * nums[i];

    int ans = f;

    for (int i = nums.length - 1; i >= 0; --i) {
      f += sum - nums.length * nums[i];
      ans = Math.max(ans, f);
    }

    return ans;
  }
}

Problem Description

The Rotate Function problem is akin to rotating a pizza without losing any toppings. Given an array of integers, the goal is to find the maximum value of a function that depends on the rotation of this array. Each rotation changes the position of the elements, and your task is to determine the best rotation that maximizes the function value.

In simpler terms, given an array nums, compute the maximum value of the function:

F(k) = ∑(nums[i] * i) for all possible rotations of the array.

Approach Explanation

The code begins by calculating the initial value of the function F(0). It then iteratively computes the value of the function for each rotation by adjusting the previous value based on the sum of the array and the last element being rotated out. This approach avoids recalculating the entire sum for each rotation, enhancing efficiency.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n)
Space Complexity	O(1)

Real-World Example

Consider a rotating billboard displaying various advertisements. Each rotation alters the position of the ads, and the objective is to find the best position that maximizes visibility (or revenue). The Rotate Function problem mirrors this scenario; the aim is to find the optimal rotation of the array that maximizes the function value, similar to determining the best angle for your billboard.