Rotate Function

Medium
438.

Rotate Function

Rotate Function is a medium coding problem on arrays, dynamic programming and math, asked in Amazon and Google interviews.

You are given an integer array nums of length n. Let arrK be nums rotated clockwise by k positions, and define

F(k) = 0 * arrK[0] + 1 * arrK[1] + … + (n - 1) * arrK[n - 1]

Return the maximum of F(0) … F(n - 1).

Example 1

Input
nums = [4,3,2,6]
Output
26
Explanation
F(3) = 0*6 + 1*4 + 2*3 + 3*2 = 26.

Example 2

Input
nums = [100]
Output
0

Example 3

Input
nums = [1,2]
Output
2

Constraints

  • 1 <= nums.length <= 40
  • -100 <= nums[i] <= 100
  • The answer fits in a signed 32-bit integer.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxRotateFunction = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Rotate Function — Solution in Python, Java & C++

Rotate Function solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Rotate Function is a medium coding problem on arrays, dynamic programming and math, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Dynamic Programming, Math
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given an integer array nums of length n. Let arrK be nums rotated clockwise by k positions, and define

F(k) = 0 * arrK[0] + 1 * arrK[1] + … + (n - 1) * arrK[n - 1]

Return the maximum of F(0) … F(n - 1).

Example 1

Input: nums = [4,3,2,6]
Output: 26
Explanation: F(3) = 0*6 + 1*4 + 2*3 + 3*2 = 26.

Example 2

Input: nums = [100]
Output: 0

Example 3

Input: nums = [1,2]
Output: 2

Constraints

  • 1 <= nums.length <= 40
  • -100 <= nums[i] <= 100
  • The answer fits in a signed 32-bit integer.

Hints for Rotate Function

  1. Hint 1

    Computing every F(k) from scratch is O(n²) — relate consecutive values instead.

  2. Hint 2

    Rotating by one adds the whole sum once and drops one element's full n * value contribution.

  3. Hint 3

    So F(k) = F(k - 1) + sum - n * nums[n - k].

How to solve Rotate Function

Relate consecutive rotations: F(k) = F(k-1) + sum - n · nums[n-k], so all n values come from one pass after computing F(0).

Approach

  1. Compute total and F(0).
  2. For k from 1 to n-1, F(k) = F(k-1) + total - n · nums[n-k]; track the max.

Why it works

Rotating right by one increases every element's coefficient by 1 (adding total) except the element that wraps from coefficient n - 1 to 0 (subtracting n · value).

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Recomputing each F(k) from scratch is O(n²).

Reference solution

Python

def maxRotateFunction(nums) -> int:
    n = len(nums)
    total = sum(nums)
    current = sum(i * x for i, x in enumerate(nums))
    best = current
    for k in range(1, n):
        current = current + total - n * nums[n - k]
        best = max(best, current)
    return best

Java

public static int maxRotateFunction(int[] nums) {
    int n = nums.length;
    int total = 0, current = 0;
    for (int i = 0; i < n; i++) {
        total += nums[i];
        current += i * nums[i];
    }
    int best = current;
    for (int k = 1; k < n; k++) {
        current = current + total - n * nums[n - k];
        best = Math.max(best, current);
    }
    return best;
}

C++

int maxRotateFunction(vector<int>& nums) {
    int n = (int) nums.size();
    int total = 0, current = 0;
    for (int i = 0; i < n; i++) {
        total += nums[i];
        current += i * nums[i];
    }
    int best = current;
    for (int k = 1; k < n; k++) {
        current = current + total - n * nums[n - k];
        best = max(best, current);
    }
    return best;
}

JavaScript

var maxRotateFunction = function(nums) {
    const n = nums.length;
    let total = 0;
    let current = 0;
    for (let i = 0; i < n; i++) {
        total += nums[i];
        current += i * nums[i];
    }
    let best = current;
    for (let k = 1; k < n; k++) {
        current = current + total - n * nums[n - k];
        if (current > best) best = current;
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming