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] <= 100The answer fits in a signed 32-bit integer.
Hints for Rotate Function
Hint 1
Computing every
F(k)from scratch is O(n²) — relate consecutive values instead.Hint 2
Rotating by one adds the whole sum once and drops one element's full
n * valuecontribution.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
- Compute
totalandF(0). - For
kfrom 1 ton-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 isO(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 bestJava
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