Rotate Function solution and explanation
Google
9 more videos on this problem
Rotate Function | Detailed with Proof | Leetcode 396 | codestorywithMIKcodestorywithMIK · 25:54 · 6K views
Leetcode 396. Rotate FunctionCodeItUp · 7:31 · 3K views
Leetcode 396. Rotate FunctionElite Code · 17:13 · 1K views
Leetcode 396 Rotate FunctionMath Geeks · 5:33 · 1K views
396. Rotate Function | Leetcode Daily - PythonLeetcode Daily · 8:24 · 1K views
396. Rotate Function (Leetcode Medium)Programming Live with Larry · 8:41 · 611 views
LeetCode 396 Rotate Function Explained | O(n) Trick You Must Know 🔥ExpertFunda · 20:28 · 515 views
Rotate Function | LeetCode 396 - Pythonimpoldev · 10:14 · 328 views
Rotate Function | LeetCode 396Streak To Scale · 4:57 · 112 views
Rotate Function | Leetcode - 396Shivam Gupta · 14:40 · 70 views
The problem
You are given an integer array nums of length n.
Assume arrk to be an array obtained by rotating nums by k positions clock-wise. We define the rotation function F on nums as follow:
F(k) = 0 * arrk[0] + 1 * arrk[1] + ... + (n - 1) * arrk[n - 1].
Return the maximum value of F(0), F(1), ..., F(n-1).
The test cases are generated so that the answer fits in a 32-bit integer.
Example 1:
Input: nums = [4,3,2,6] Output: 26 Explanation: F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25 F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16 F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23 F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26 So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.
Example 2:
Input: nums = [100] Output: 0
Constraints:
n == nums.length1 <= n <= 105-100 <= nums[i] <= 100
Approach overview
Problem Overview: Given an integer array nums, define a rotation function F(k) where the array is rotated k positions and each element is multiplied by its index. The goal is to compute the maximum value among all rotations.
Approach 1: Brute Force Rotation Simulation (Time: O(n^2), Space: O(1))
Directly simulate every rotation and compute the function value from scratch. For each rotation k, iterate through the array and calculate F(k) = sum(i * rotated[i]). Rotating or indexing elements for every k requires scanning the entire array, which results in O(n) work per rotation and n total rotations. The approach is straightforward and useful for validating correctness, but it becomes slow when n grows because the total runtime reaches O(n^2). This method mainly relies on basic array traversal.
Approach 2: Mathematical Recurrence Optimization (Time: O(n), Space: O(1))
The key observation is that consecutive rotation values are related. If F(k) is known, the next rotation can be derived using a recurrence instead of recomputing everything. Let S be the total sum of all elements. After rotating once, each element’s index increases by 1 except the last element which moves to index 0. This leads to the formula F(k) = F(k-1) + S - n * nums[n-k]. Start by computing F(0) and the total sum in one pass. Then iterate through rotations using the recurrence to update the value in constant time. This transforms the problem into a linear scan using ideas from math and recurrence-style reasoning similar to dynamic programming. The algorithm evaluates all rotations in O(n) time while using only constant extra space.
Recommended for interviews: The mathematical recurrence approach is the expected solution. Interviewers often want to see whether you recognize the relationship between consecutive rotations and avoid recomputing the weighted sum each time. Implementing the brute force version first demonstrates understanding of the rotation function, but deriving the recurrence and reducing the complexity to O(n) shows strong problem‑solving skills.
Approach 1: Brute Force Approach
The brute force approach involves recalculating the rotation function F(k) for each rotation k from 0 to n-1. For each k, simulate the rotation and compute the result using the definition provided. This, however, can be time-consuming for larger arrays due to recalculating rotations or the function from scratch each time.
def maxRotateFunction(nums):
max_val = float('-inf')
n = len(nums)
for k in range(n):
current_sum = 0
for i in range(n):
current_sum += i * nums[(i + k) % n]
max_val = max(max_val, current_sum)
return max_val
nums = [4, 3, 2, 6]
print(maxRotateFunction(nums))import java.util.*;
public class Main {
public static int maxRotateFunction(int[] nums) {
int max = Integer.MIN_VALUE;
int n = nums.length;
for (int k = 0; k < n; ++k) {
int current = 0;
for (int i = 0; i < n; ++i) {
current += i * nums[(i + k) % n];
}
max = Math.max(max, current);
}
return max;
}
public static void main(String[] args) {
int[] nums = {4, 3, 2, 6};
System.out.println(maxRotateFunction(nums));
}
}#include <iostream>
#include <vector>
using namespace std;
int maxRotateFunction(vector<int>& nums) {
int max = INT_MIN;
int n = nums.size();
for (int k = 0; k < n; ++k) {
int current = 0;
for (int i = 0; i < n; ++i) {
current += i * nums[(i + k) % n];
}
max = max > current ? max : current;
}
return max;
}
int main() {
vector<int> nums = {4, 3, 2, 6};
cout << maxRotateFunction(nums) << endl;
return 0;
}function maxRotateFunction(nums) {
let max = Number.MIN_SAFE_INTEGER;
const n = nums.length;
for (let k = 0; k < n; ++k) {
let currentSum = 0;
for (let i = 0; i < n; ++i) {
currentSum += i * nums[(i + k) % n];
}
max = Math.max(max, currentSum);
}
return max;
}
const nums = [4, 3, 2, 6];
console.log(maxRotateFunction(nums));#include <stdio.h>
#include <string.h>
int maxRotateFunction(int* nums, int numsSize) {
int max = INT_MIN;
for (int k = 0; k < numsSize; k++) {
int current = 0;
for (int i = 0; i < numsSize; i++) {
current += i * nums[(i + k) % numsSize];
}
if (current > max) max = current;
}
return max;
}
int main() {
int nums[] = {4, 3, 2, 6};
int result = maxRotateFunction(nums, 4);
printf("%d\n", result);
return 0;
}using System;
class Program {
public static int MaxRotateFunction(int[] nums) {
int max = int.MinValue;
int n = nums.Length;
for (int k = 0; k < n; ++k) {
int current = 0;
for (int i = 0; i < n; ++i) {
current += i * nums[(i + k) % n];
}
max = Math.Max(max, current);
}
return max;
}
static void Main() {
int[] nums = {4, 3, 2, 6};
Console.WriteLine(MaxRotateFunction(nums));
}
}Using Python, this function loops through each rotation, calculates the value of F(k), and tracks the maximum encountered value. It's a direct translation of the brute force approach.
Time Complexity: O(n^2)
Space Complexity: O(1)
Approach 2: Optimized Approach Using Mathematical Formula
This optimized approach utilizes a mathematical relationship between F(k) and F(k+1). Notice how the array rotates and calculate the sum considering the differences. Thereby avoiding recalculation of entire sets of sums, utilizing already computed values dynamically.
def maxRotateFunction(nums):
n = len(nums)
sum_all = sum(nums)
f = sum(i * num for i, num in enumerate(nums))
max_val = f
for k in range(1, n):
f = f + sum_all - n * nums[n - k]
max_val = max(max_val, f)
return max_val
nums = [4, 3, 2, 6]
print(maxRotateFunction(nums))public class Main {
public static int maxRotateFunction(int[] nums) {
int sum = 0, f = 0, n = nums.length;
for (int i = 0; i < n; ++i) {
sum += nums[i];
f += i * nums[i];
}
int max = f;
for (int k = 1; k < n; ++k) {
f = f + sum - n * nums[n - k];
max = Math.max(max, f);
}
return max;
}
public static void main(String[] args) {
int[] nums = {4, 3, 2, 6};
System.out.println(maxRotateFunction(nums));
}
}#include <iostream>
#include <vector>
using namespace std;
int maxRotateFunction(vector<int>& nums) {
int sum = 0, f = 0, n = nums.size();
for (int i = 0; i < n; ++i) {
sum += nums[i];
f += i * nums[i];
}
int max = f;
for (int k = 1; k < n; ++k) {
f = f + sum - n * nums[n-k];
max = (f > max) ? f : max;
}
return max;
}
int main() {
vector<int> nums = {4, 3, 2, 6};
cout << maxRotateFunction(nums) << endl;
return 0;
}function maxRotateFunction(nums) {
const n = nums.length;
let sum = nums.reduce((acc, val) => acc + val, 0);
let f = nums.reduce((acc, val, idx) => acc + idx * val, 0);
let max = f;
for (let k = 1; k < n; ++k) {
f = f + sum - n * nums[n - k];
max = Math.max(max, f);
}
return max;
}
const nums = [4, 3, 2, 6];
console.log(maxRotateFunction(nums));#include <stdio.h>
int maxRotateFunction(int* nums, int numsSize) {
int sum = 0, f = 0;
for(int i = 0; i < numsSize; i++) {
sum += nums[i];
f += i * nums[i];
}
int max = f;
for(int k = 1; k < numsSize; k++) {
f += sum - numsSize * nums[numsSize - k];
if(f > max) max = f;
}
return max;
}
int main() {
int nums[] = {4,3,2,6};
int result = maxRotateFunction(nums, 4);
printf("%d\n", result);
return 0;
}using System;
class Program {
public static int MaxRotateFunction(int[] nums) {
int n = nums.Length;
int sum = 0, f = 0;
for (int i = 0; i < n; ++i) {
sum += nums[i];
f += i * nums[i];
}
int max = f;
for (int k = 1; k < n; ++k) {
f = f + sum - n * nums[n - k];
max = Math.Max(max, f);
}
return max;
}
static void Main() {
int[] nums = {4, 3, 2, 6};
Console.WriteLine(MaxRotateFunction(nums));
}
}Python solution optimizes by computing initial rotation function and then iteratively updating it using the formula for reduced overhead, involving list sum and element contributions at each rotation step.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 3: Default Approach
function maxRotateFunction(nums: number[]): number {
const n = nums.length;
const sum = nums.reduce((r, v) => r + v);
let res = nums.reduce((r, v, i) => r + v * i, 0);
let pre = res;
for (let i = 1; i < n; i++) {
pre = pre - (sum - nums[i - 1]) + nums[i - 1] * (n - 1);
res = Math.max(res, pre);
}
return res;
}func maxRotateFunction(nums []int) int {
f, s, n := 0, 0, len(nums)
for i, v := range nums {
f += i * v
s += v
}
ans := f
for i := 1; i < n; i++ {
f = f + s - n*nums[n-i]
if ans < f {
ans = f
}
}
return ans
}impl Solution {
pub fn max_rotate_function(nums: Vec<i32>) -> i32 {
let n = nums.len();
let sum: i32 = nums.iter().sum();
let mut pre: i32 = nums.iter().enumerate().map(|(i, &v)| (i as i32) * v).sum();
(0..n)
.map(|i| {
let res = pre;
pre = pre - (sum - nums[i]) + nums[i] * ((n - 1) as i32);
res
})
.max()
.unwrap_or(0)
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2) |
| Optimized Approach Using Mathematical Formula | Time Complexity: O(n) |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Rotation Simulation | O(n^2) | O(1) | Useful for understanding the definition of the rotation function or verifying correctness on small inputs |
| Mathematical Recurrence Optimization | O(n) | O(1) | Best choice for interviews and large arrays since each rotation value is derived in constant time |
Frequently asked questions
Is Rotate Function easy or hard?
Rotate Function is typically classified as a medium difficulty problem. The brute force idea is easy to implement, but identifying the recurrence relation that enables an O(n) solution requires deeper insight into how rotations affect index-weighted sums.
Rotate Function Python/Java solution
Both Python and Java implementations follow the same logic: compute the total sum and F(0), then iterate through rotations applying the recurrence formula. The loop updates the rotation value in constant time and tracks the maximum result.
How to solve Rotate Function in O(n)?
First compute the total sum of the array and the value of F(0) using a single pass. Then iterate through the remaining rotations and update the value using the recurrence F(k) = F(k-1) + sum - n * nums[n-k]. Each step takes constant time, so evaluating all rotations takes O(n).
What is the best approach for Rotate Function?
The optimal approach uses a mathematical recurrence relation between consecutive rotations. After computing F(0) and the total sum of the array, each next value can be derived using F(k) = F(k-1) + sum - n * nums[n-k]. This reduces the complexity from O(n^2) to O(n) time with O(1) extra space.
Is Rotate Function asked at Google/Amazon/Meta?
Rotate Function represents a common interview pattern where brute force must be optimized using mathematical observations or dynamic programming style recurrence. Variants of this weighted rotation or cyclic transformation problem have appeared in interviews at large tech companies including Google and Amazon.
What data structure is used in Rotate Function?
The problem primarily uses arrays. The optimized solution also relies on mathematical reasoning and recurrence relationships between rotations, which is conceptually similar to dynamic programming where the next state is derived from the previous state.
What is the time complexity of Rotate Function?
The brute force solution runs in O(n^2) time because the rotation function is recomputed for every rotation. The optimized solution runs in O(n) time by reusing the previous rotation value through a recurrence formula. Both approaches use O(1) extra space.