Rotate Function

MEDIUM

Description

You are given an integer array nums of length n.

Assume arr_k 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 * arr_k[0] + 1 * arr_k[1] + ... + (n - 1) * arr_k[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 <= 10⁵
-100 <= nums[i] <= 100

Approaches

Checkout 2 different approaches to solve Rotate Function. Click on different approaches to view the approach and algorithm in detail.

Brute Force by Simulating Rotations

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.

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 Analysis

Time Complexity: 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 Complexity: O(n) - In each iteration of the outer loop, a new array of size `n` is created to store the rotated version of `nums`.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Rotate Function. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Rotate Function

Patterns:

MathDynamic Programming

Data Structures:

Array