Scale Engineer

Rotate Function

Med
#0383Time: O(n^2) - The outer loop runs `n` times for each rotation. Inside, creating the rotated array takes `O(n)` time, and calculating `F(k)` also takes `O(n)` time. Thus, the total complexity is `n * (O(n) + O(n)) = O(n^2)`.Space: O(n) - In each iteration of the outer loop, a new array of size `n` is created to store the rotated version of `nums`.
Patterns
MathDynamic Programming
Data structures
Array

Prompt

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.length
  • 1 <= n <= 105
  • -100 <= nums[i] <= 100

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly follows the problem definition. It iterates through all possible n rotations. For each rotation k, it first constructs the rotated array arr_k and then computes the rotation function F(k) by summing the products i * arr_k[i]. The maximum value found among all F(k) is the result.

Algorithm

  • Initialize maxF to the smallest possible integer value.
  • Loop for k from 0 to n-1:
    • Create a temporary array rotatedNums of size n.
    • Populate rotatedNums by simulating the rotation: for each i from 0 to n-1, set rotatedNums[(i + k) % n] = nums[i].
    • Initialize currentF = 0.
    • Calculate F(k): for each j from 0 to n-1, add j * rotatedNums[j] to currentF.
    • Update maxF = Math.max(maxF, currentF).
  • Return maxF.

Walkthrough

The core idea is to simulate the process described in the problem. We generate each of the n possible rotated arrays and calculate the rotation function for each one, keeping track of the maximum value.

Algorithm:

  • Initialize maxF to the smallest possible integer value.
  • Loop for k from 0 to n-1:
    • Create a temporary array rotatedNums of size n.
    • Populate rotatedNums by simulating the rotation: for each i from 0 to n-1, set rotatedNums[(i + k) % n] = nums[i].
    • Initialize currentF = 0.
    • Calculate F(k): for each j from 0 to n-1, add j * rotatedNums[j] to currentF.
    • Update maxF = Math.max(maxF, currentF).
  • Return maxF.
class Solution {    public int maxRotateFunction(int[] nums) {        int n = nums.length;        if (n <= 1) {            return 0;        }        int maxF = Integer.MIN_VALUE;         for (int k = 0; k < n; k++) {            // 1. Create the rotated array for rotation k            int[] rotatedNums = new int[n];            for (int i = 0; i < n; i++) {                rotatedNums[(i + k) % n] = nums[i];            }             // 2. Calculate F(k) for the rotated array            int currentF = 0;            for (int i = 0; i < n; i++) {                currentF += i * rotatedNums[i];            }                        // 3. Update the maximum            maxF = Math.max(maxF, currentF);        }        return maxF;    }}

Complexity

Time

O(n^2) - The outer loop runs `n` times for each rotation. Inside, creating the rotated array takes `O(n)` time, and calculating `F(k)` also takes `O(n)` time. Thus, the total complexity is `n * (O(n) + O(n)) = O(n^2)`.

Space

O(n) - In each iteration of the outer loop, a new array of size `n` is created to store the rotated version of `nums`.

Trade-offs

Pros

  • Simple to understand and implement.

  • Directly translates the problem statement into code.

Cons

  • Inefficient for large inputs due to its quadratic time complexity.

  • With n up to 10^5, an O(n^2) solution will result in a 'Time Limit Exceeded' error.

Solutions

public class Rotate_Function { class Solution { public int maxRotateFunction ( int [] A ) { int prevValue = 0 ; int sum = 0 ; int n = A . length ; for ( int i = 0 ; i < n ; ++ i ) { sum += A [ i ]; // get: 1A+1B+1C+1D+... prevValue += i * A [ i ]; // get: F(0) first } int result = prevValue ; for ( int i = 1 ; i < n ; i ++) { // start from index=1 prevValue = prevValue + sum - n * A [ n - i ]; result = Math . max ( result , prevValue ); } return result ; } } } ############ class Solution { public int maxRotateFunction ( int [] nums ) { int f = 0 ; int s = 0 ; int n = nums . length ; for ( int i = 0 ; i < n ; ++ i ) { f += i * nums [ i ]; s += nums [ i ]; } int ans = f ; for ( int i = 1 ; i < n ; ++ i ) { f = f + s - n * nums [ n - i ]; ans = Math . max ( ans , f ); } return ans ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem