LeetCode 396: Rotate Function

Problem Restatement

We are given an integer array nums of length n.

For each rotation k, define F(k) as:

F(k) = 0 * arr[k][0] + 1 * arr[k][1] + ... + (n - 1) * arr[k][n - 1]

where arr[k] is nums rotated clockwise by k positions.

We need to return the maximum value among:

F(0), F(1), ..., F(n - 1)

The answer is guaranteed to fit in a 32-bit signed integer. The constraints are 1 <= n <= 10^5 and -100 <= nums[i] <= 100.

Input and Output

Example function shape:

def maxRotateFunction(nums: list[int]) -> int:
    ...

Examples

Example 1:

nums = [4, 3, 2, 6]

The rotations are:

F(0): [4, 3, 2, 6]
F(1): [6, 4, 3, 2]
F(2): [2, 6, 4, 3]
F(3): [3, 2, 6, 4]

Compute each value:

F(0) = 0*4 + 1*3 + 2*2 + 3*6 = 25
F(1) = 0*6 + 1*4 + 2*3 + 3*2 = 16
F(2) = 0*2 + 1*6 + 2*4 + 3*3 = 23
F(3) = 0*3 + 1*2 + 2*6 + 3*4 = 26

The maximum is:

26

Example 2:

nums = [100]

There is only one rotation:

F(0) = 0 * 100 = 0

So the answer is:

0

First Thought: Simulate Every Rotation

A direct solution is:

1. Build every rotated array.
2. Compute its rotation function.
3. Track the maximum.

For each rotation, computing F(k) costs O(n).

There are n rotations.

So the total time is:

O(n^2)

With n up to 10^5, this is too slow.

Key Insight

We can derive F(k) from F(k - 1) in constant time.

Let:

total = sum(nums)

Consider this example:

nums = [4, 3, 2, 6]

For F(0):

0*4 + 1*3 + 2*2 + 3*6

For F(1), the last element 6 moves to the front:

0*6 + 1*4 + 2*3 + 3*2

Every element except the moved element has its multiplier increased by 1.

Adding total increases every multiplier by 1.

But the moved element was at multiplier n - 1 and becomes multiplier 0.

So we subtract n * moved.

The recurrence is:

F(k) = F(k - 1) + total - n * nums[n - k]

For k = 1, the moved element is nums[n - 1].

For k = 2, the moved element is nums[n - 2].

And so on.

Algorithm

First compute:

total = sum(nums)
current = F(0)

Then initialize:

best = current

For each rotation k from 1 to n - 1:

1. The moved element is:

   nums[n - k]
2. Update:

   current = current + total - n * nums[n - k]
3. Update the answer:

   best = max(best, current)

Return best.

Correctness

F(0) is computed directly from the original array, so it is correct.

For each next rotation, the last element of the previous rotated array moves to the front. Every other element shifts one position to the right, increasing its coefficient by 1.

Adding total to the previous function value accounts for increasing every element’s coefficient by 1.

However, the moved element should not gain one coefficient. It moves from coefficient n - 1 to coefficient 0. Adding total temporarily gives it coefficient n, so subtracting n * moved corrects it.

Therefore the recurrence computes each F(k) exactly from F(k - 1).

The algorithm computes every rotation value from F(0) through F(n - 1) and keeps the maximum. Therefore it returns the required maximum rotation function value.

Complexity

Let n = len(nums).

Implementation

class Solution:
    def maxRotateFunction(self, nums: list[int]) -> int:
        n = len(nums)

        total = sum(nums)
        current = 0

        for i, num in enumerate(nums):
            current += i * num

        best = current

        for k in range(1, n):
            moved = nums[n - k]
            current = current + total - n * moved
            best = max(best, current)

        return best

Code Explanation

We store the array length:

n = len(nums)

Then compute the sum of all values:

total = sum(nums)

Now compute F(0) directly:

current = 0

for i, num in enumerate(nums):
    current += i * num

The first candidate answer is F(0):

best = current

Then compute the remaining rotations using the recurrence:

for k in range(1, n):
    moved = nums[n - k]
    current = current + total - n * moved
    best = max(best, current)

Finally:

return best

Testing

def test_solution():
    s = Solution()

    assert s.maxRotateFunction([4, 3, 2, 6]) == 26
    assert s.maxRotateFunction([100]) == 0
    assert s.maxRotateFunction([0, 0, 0]) == 0
    assert s.maxRotateFunction([1, 2, 3]) == 8
    assert s.maxRotateFunction([-1, -2, -3]) == -5
    assert s.maxRotateFunction([5, -1, 2]) == 9

    print("all tests passed")

test_solution()

Test meaning: