Rotate Function: Math Pattern in Rotations

You are given an integer array nums of length n. Define the rotation function F(k) as:

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

where nums_k is the array nums rotated by k positions. Return the maximum value of F(0), F(1), ..., F(n-1).

This is LeetCode 396: Rotate Function, and the brute force approach of computing every rotation explicitly is O(n^2). The trick is a math recurrence that lets you derive each F(k) from F(k-1) in O(1), bringing the whole solution down to O(n).

Understanding the rotation

When you rotate the array by one position, every element shifts one index to the right, and the last element wraps around to index 0. That means every element's weight (its index) increases by 1, except for the last element whose weight drops from n-1 all the way to 0.

If you think about what that does to the sum:

• Every element gets +1 to its weight, adding totalSum to the total
• The element that wraps to position 0 loses its full weight of n, so you subtract n * lastElement

That gives us the recurrence:

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

This is the entire insight. Once you have F(0) and totalSum, every subsequent F(k) is just one addition and one subtraction.

The brute force approach

Before the optimization, let's see why the naive approach is too slow. For each rotation, you'd build the rotated array and compute the weighted sum:

def maxRotateFunction(nums):
    n = len(nums)
    best = float('-inf')

    for k in range(n):
        total = 0
        for i in range(n):
            total += i * nums[(i - k) % n]
        best = max(best, total)

    return best

This is O(n^2). For n = 100,000, that is 10 billion operations. Way too slow.

The O(n) solution

With the recurrence in hand, the code is short:

def maxRotateFunction(nums):
    n = len(nums)
    total_sum = sum(nums)
    f = sum(i * nums[i] for i in range(n))
    best = f

    for k in range(1, n):
        f = f + total_sum - n * nums[n - k]
        best = max(best, f)

    return best

Two passes over the array (one for totalSum and F(0), one for the remaining F(k) values), and a running max to track the best. That is it.

Step-by-step walkthrough

Let's trace through nums = [4, 3, 2, 6] step by step to see the recurrence in action.

The maximum across all rotations is F(3) = 26. We found it in O(n) time without ever building a rotated array.

Why the recurrence works

The proof is clean. Write out the definitions:

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

F(k-1) = 0*nums_{k-1}[0] + 1*nums_{k-1}[1] + ... + (n-1)*nums_{k-1}[n-1]

When you rotate by one more position, nums_k[i] = nums_{k-1}[i-1] for i > 0, and nums_k[0] = nums_{k-1}[n-1].

Computing F(k) - F(k-1):

• Each element except the one that wrapped gains +1 to its coefficient, contributing +totalSum
• The wrapped element had coefficient n-1 and now has coefficient 0, contributing -(n-1) * wrappedElement
• But we also added the wrapped element once in the +totalSum part, so the net effect on the wrapped element is -(n-1) * wrappedElement - wrappedElement + wrappedElement = -n * wrappedElement + wrappedElement

Wait, let's be more careful. The net change is:

F(k) - F(k-1) = totalSum - n * wrappedElement

This holds because all n elements each gain +1 weight (that is +totalSum), and then the wrapped element drops from weight n-1 to weight 0 (losing n in total, not just n-1, because we already counted it gaining +1 in the totalSum term).

Complexity analysis

Computing totalSum and F(0) each take O(n). The loop over k = 1..n-1 does O(1) work per iteration. Total: O(n). We use only a handful of variables, so space is O(1).

The building blocks

This problem relies on two reusable patterns:

1. Recurrence derivation

Instead of recomputing a sum from scratch after each transformation, figure out how the transformation changes the sum. This is the same idea behind prefix sums, difference arrays, and sliding window sums. The question is always: "What changed between step k-1 and step k, and can I express that change in O(1)?"

2. Running max

As you iterate through the F(k) values, you maintain a best variable that tracks the maximum seen so far. This is the same running-max pattern from Maximum Subarray and the running-min pattern from Best Time to Buy and Sell Stock. One variable, one comparison per step.

These two building blocks, the O(1) recurrence and the running max, combine into a clean linear solution.

Edge cases

Before submitting, verify your solution handles these:

• Single element [5]: F(0) = 0. There is only one rotation, and the weight for index 0 is always 0.
• All zeros [0, 0, 0]: every F(k) = 0. The answer is 0.
• Negative numbers [-1, -2, -3]: the recurrence still works. Negatives do not break the math.
• Large arrays (n up to 100,000): the O(n) solution handles this easily. The O(n^2) brute force would time out.
• Two elements [a, b]: F(0) = b, F(1) = a. The answer is max(a, b).

From understanding to recall

The recurrence F(k) = F(k-1) + totalSum - n * nums[n-k] is easy to understand when you read it. Deriving it from scratch under interview pressure is a different skill. You need to have the pattern of "figure out what changed between consecutive states" in your toolkit, ready to deploy without hesitation.

Spaced repetition helps you bridge that gap. You solve this problem once, internalize the recurrence derivation technique, and then revisit it at increasing intervals. After a few reps, the pattern is no longer something you reconstruct. It is something you recognize immediately when you see a problem about sums over transformations.

The recurrence derivation pattern and the running max are building blocks that show up across dozens of problems. Learning them individually and drilling them with spaced repetition is far more efficient than solving problems one at a time and hoping the connections stick.

Related posts

• Rotate Array - The foundational rotation problem, where the triple reverse trick handles in-place rotation in O(n)
• Product of Array Except Self - Another array problem where clever math avoids recomputing sums from scratch
• Maximum Subarray - Uses the same running-max pattern to track the best value across a single pass