LeetCode 396 - Rotate Function

LeetCode Problem 396

Difficulty: 🟡 Medium
Topics: Array, Math, Dynamic Programming

Solution

Problem Understanding

The problem defines a special value called the rotation function for an array. Given an integer array nums of length n, we rotate the array clockwise by k positions to create a new array arrk. For every possible rotation from 0 to n - 1, we compute:

$$F(k) = 0 \cdot arr_k[0] + 1 \cdot arr_k[1] + 2 \cdot arr_k[2] + \dots + (n-1) \cdot arr_k[n-1]$$

The task is to return the maximum value among all possible rotation functions.

A clockwise rotation means the last element moves to the front. For example, if:

nums = [4,3,2,6]

then:

Rotation 1 -> [6,4,3,2]
Rotation 2 -> [2,6,4,3]
Rotation 3 -> [3,2,6,4]

For each rotated version, we calculate the weighted sum where the weight equals the index.

The constraints are important because they determine what kinds of solutions are feasible:

• The array length can be as large as 10^5
• Each element is between -100 and 100
• The result always fits within a 32-bit integer

An O(n^2) solution may appear straightforward at first, but with n = 100000, it would require roughly 10^10 operations, which is far too slow. This strongly suggests that we need a linear-time or near-linear-time approach.

There are several important edge cases to consider:

• A single-element array, where every rotation is identical and the answer must be 0
• Arrays containing negative numbers, where the maximum rotation function may not correspond to the visually largest arrangement
• Arrays with all identical values, where every rotation produces the same result
• Large arrays, where recomputing the rotation function from scratch for every rotation becomes prohibitively expensive

The problem guarantees that the array is non-empty, so we never need to handle an empty input.

Approaches

Brute Force Approach

The most direct solution is to explicitly generate every rotation and compute its rotation function independently.

For each rotation k:

1. Rotate the array clockwise by k
2. Compute the weighted sum
3. Track the maximum value encountered

This approach is correct because it directly follows the problem definition. Since the problem asks for the maximum among all rotation functions, evaluating every possible rotation guarantees correctness.

However, the performance is poor. There are n rotations, and computing each rotation function requires O(n) work. That produces an overall complexity of O(n^2).

With n = 100000, this approach is too slow.

Optimal Approach

The key observation is that consecutive rotation functions are mathematically related.

Suppose:

$$F(0) = 0 \cdot nums[0] + 1 \cdot nums[1] + \dots + (n-1) \cdot nums[n-1]$$

When we rotate the array once clockwise, the last element moves to the front. Instead of recomputing the entire weighted sum from scratch, we can derive the next value from the previous one.

Let:

• totalSum = sum(nums)
• F(k) be the current rotation value

Then the recurrence relation is:

$$F(k) = F(k-1) + totalSum - n \cdot nums[n-k]$$

This formula works because after rotation:

• Every element's index increases by 1
• Except the element moved to the front, whose contribution becomes 0

Using this recurrence, each new rotation value can be computed in constant time.

That reduces the total complexity to O(n).

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1) or O(n)	Recomputes every rotation independently
Optimal	O(n)	O(1)	Uses recurrence relation between rotations

Algorithm Walkthrough

1. Compute the total sum of the array.

We store:

totalSum = sum(nums)

This value is reused repeatedly in the recurrence formula, so precomputing it avoids redundant work. 2. Compute the initial rotation function F(0).

We calculate:

$$F(0) = \sum_{i=0}^{n-1} i \cdot nums[i]$$

This serves as the starting point for all later computations. 3. Initialize the answer.

Since F(0) is a valid rotation value, we start with:

maxValue = F(0)

4. Generate subsequent rotation values using the recurrence relation.

For each rotation from 1 to n - 1, compute:

$$F(k) = F(k-1) + totalSum - n \cdot nums[n-k]$$

Here:

• F(k-1) is the previous rotation value
• totalSum accounts for every element shifting one position forward
• nums[n-k] is the element moved from the end to the front, whose weighted contribution changes significantly

5. Update the maximum value after each computation.

Since every rotation function is considered exactly once, the largest value encountered is the final answer.

Why it works

The recurrence relation correctly models how the weighted sum changes after a clockwise rotation.

When rotating:

• Every element except one moves one index forward, increasing its contribution by its value
• The last element wraps around to index 0, losing its previous contribution of (n - 1) * value

The recurrence formula precisely captures this net change, allowing every rotation function to be derived from the previous one in constant time.

Because we evaluate every possible rotation exactly once, the algorithm always returns the correct maximum value.

Python Solution

from typing import List

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

        total_sum = sum(nums)

        current_value = 0
        for index, value in enumerate(nums):
            current_value += index * value

        max_value = current_value

        for rotation in range(1, n):
            current_value = (
                current_value
                + total_sum
                - n * nums[n - rotation]
            )

            max_value = max(max_value, current_value)

        return max_value

The implementation begins by computing the array length and total sum. The total sum is reused during every rotation update, so calculating it once improves efficiency.

Next, the code computes F(0) by iterating through the array with enumerate. Each element contributes index * value to the weighted sum.

The variable max_value stores the best rotation function value seen so far.

The main loop then iterates through all remaining rotations. Instead of rebuilding the rotated array, the recurrence relation updates the current rotation value in constant time.

The expression:

current_value + total_sum - n * nums[n - rotation]

implements the mathematical transition from F(k-1) to F(k).

Finally, the algorithm returns the maximum value found across all rotations.

Go Solution

func maxRotateFunction(nums []int) int {
    n := len(nums)

    totalSum := 0
    currentValue := 0

    for i, value := range nums {
        totalSum += value
        currentValue += i * value
    }

    maxValue := currentValue

    for rotation := 1; rotation < n; rotation++ {
        currentValue = currentValue +
            totalSum -
            n*nums[n-rotation]

        if currentValue > maxValue {
            maxValue = currentValue
        }
    }

    return maxValue
}

The Go implementation follows the same logic as the Python version.

A few Go-specific details are worth noting:

• Go uses explicit integer variables instead of Python's arbitrary-precision integers
• The problem guarantees the result fits within a 32-bit integer, so standard int usage is safe
• Slices are used directly, no array copying or rotation is performed
• The recurrence relation allows all computations to remain in constant extra space

Worked Examples

Example 1

nums = [4,3,2,6]

First compute:

Variable	Value
n	4
totalSum	15

Compute F(0):

$$F(0) = 0 \cdot 4 + 1 \cdot 3 + 2 \cdot 2 + 3 \cdot 6$$

$$F(0) = 0 + 3 + 4 + 18 = 25$$

Initial state:

Rotation	Formula	Value
F(0)	Initial computation	25

Now compute subsequent rotations.

Rotation	Computation	Result
F(1)	25 + 15 - 4 × 6	16
F(2)	16 + 15 - 4 × 2	23
F(3)	23 + 15 - 4 × 3	26

Maximum value:

26

Example 2

nums = [100]

Compute:

Variable	Value
n	1
totalSum	100

Compute F(0):

$$0 \cdot 100 = 0$$

There are no additional rotations because the array contains only one element.

Final answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is processed a constant number of times
Space	O(1)	Only a few scalar variables are used

The algorithm performs one pass to compute the initial rotation value and total sum, then another pass to evaluate all remaining rotations. No auxiliary arrays or data structures are created, so the extra space usage remains constant.

Test Cases

from typing import List

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

        total_sum = sum(nums)

        current_value = 0
        for index, value in enumerate(nums):
            current_value += index * value

        max_value = current_value

        for rotation in range(1, n):
            current_value = (
                current_value
                + total_sum
                - n * nums[n - rotation]
            )

            max_value = max(max_value, current_value)

        return max_value

solution = Solution()

assert solution.maxRotateFunction([4, 3, 2, 6]) == 26  # Provided example
assert solution.maxRotateFunction([100]) == 0  # Single element
assert solution.maxRotateFunction([1, 2, 3, 4, 5]) == 40  # Increasing sequence
assert solution.maxRotateFunction([5, 5, 5, 5]) == 30  # All identical values
assert solution.maxRotateFunction([-1, -2, -3]) == -5  # All negative values
assert solution.maxRotateFunction([0, 0, 0]) == 0  # All zeros
assert solution.maxRotateFunction([1, 0, 0, 0]) == 3  # One non-zero value
assert solution.maxRotateFunction([10, -10, 10, -10]) == 20  # Mixed positive and negative
assert solution.maxRotateFunction([1, 2]) == 2  # Small two-element case
assert solution.maxRotateFunction([-100, 100]) == 100  # Boundary values

Test Case Summary

Test	Why
[4,3,2,6]	Validates the main example from the problem
[100]	Tests single-element behavior
[1,2,3,4,5]	Tests normal increasing values
[5,5,5,5]	Ensures equal rotations produce equal values
[-1,-2,-3]	Verifies handling of negative numbers
[0,0,0]	Tests zero-only arrays
[1,0,0,0]	Tests rotation impact of a single non-zero value
[10,-10,10,-10]	Tests mixed positive and negative numbers
[1,2]	Tests minimal multi-element input
[-100,100]	Tests constraint boundary values

Edge Cases

A single-element array is one of the most important edge cases. Since rotating a single element changes nothing, every rotation function value is necessarily 0. A buggy implementation might incorrectly attempt additional rotations or mishandle indexing logic. The current implementation handles this naturally because the rotation loop never executes when n == 1.

Arrays containing negative numbers can also cause subtle issues. Some solutions incorrectly assume that maximizing the rotation function means placing larger numbers at larger indices. Negative values invalidate that intuition because moving a negative number to a higher-weighted position decreases the total score. The recurrence-based solution avoids such assumptions and evaluates every rotation exactly.

Arrays where all elements are identical form another useful edge case. In this situation, every rotation produces the same array structure, so all rotation function values are equal. Some incorrect implementations may accidentally introduce drift due to indexing mistakes in the recurrence formula. Because this implementation derives each rotation mathematically from the previous one, all computed values remain consistent.

Very large arrays are also critical. With n = 100000, brute-force recomputation becomes infeasible. The optimized solution avoids constructing rotated arrays entirely and computes each new rotation value in constant time, ensuring the algorithm remains efficient even at maximum input size.