396. Rotate Function


Problem Description

In this problem, you're given an array of integers called nums. This array has n elements. The task is to perform rotations on this array and compute a certain value, called the "rotation function F", for each rotated version of the array.

A rotation consists of shifting every element of the array to the right by one position, and the last element is moved to the first position. This is a clockwise rotation. If nums is rotated by k positions clockwise, the resulting array is named arr_k.

The rotation function F for a rotation k is defined as follows:

1F(k) = 0 * arr_k[0] + 1 * arr_k[1] + ... + (n - 1) * arr_k[n - 1].

In other words, each element of the rotated array arr_k is multiplied by its index, and the results of these multiplications are summed to give F(k).

The objective is to find out which rotation (from F(0) to F(n-1)) yields the highest value of F(k) and to return this maximum value.

Intuition

The intuition behind the solution comes from observing that the rotation function F is closely related to the sum of the array and the previous value of F. Specifically, we can derive F(k) from F(k-1) by adding the sum of the array elements and then subtracting the array size multiplied by the element that just got rotated to the beginning of the array (as this element's coefficient in the rotation function decreases by n).

Here’s the thinking process:

  1. First, compute the initial value of F(0) by multiplying each index by its corresponding value in the unrotated array. This gives us the starting point for computing subsequent values of F(k).

  2. Keep track of the total sum of the array, as this will be used in computing F(k) for k > 0.

  3. Iterate through the array from k = 1 to k = n-1. In each iteration, calculate F(k) based on the previous F(k-1) by adding the total sum of the array and subtracting n times the element that was at the end of the array in the previous rotation.

  4. During each iteration, update the maximum value of F(k) found so far.

By the end of the iteration, we have considered all possible rotations and have kept track of the maximum F(k) value, which the function returns as the answer.

1
2The provided Python solution implements this thinking process:
3
4```python
5class Solution:
6    def maxRotateFunction(self, nums: List[int]) -> int:
7        # Initial calculation of F(0)
8        f = sum(i * v for i, v in enumerate(nums))
9        # Total sum of the array
10        n, s = len(nums), sum(nums)
11        # Starting with the maximum as the initial F(0)
12        ans = f
13        # Looping through the array for subsequent Fs
14        for i in range(1, n):
15            # Update F(k) based on previous value F(k-1), total sum, and subtracting the last element's contribution
16            f = f + s - n * nums[n - i]
17            # Update the answer with the max value found
18            ans = max(ans, f)
19        return ans
20
21**Learn more about [Math](/problems/math-basics) and [Dynamic Programming](/problems/dynamic_programming_intro) patterns.**
Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

What's the relationship between a tree and a graph?

Solution Approach

The solution employs a straightforward approach without any complex algorithms or data structures. It hinges on the mathematical relationship between the values of F(k) after each rotation. Let's walk through the steps, aligning them with the provided Python code snippet:

  1. Initial Value of F(0): Calculating the initial value of F(0) involves using a simple loop or in this case, a generator expression, which multiplies each element by its index and sums up these products.

    1f = sum(i * v for i, v in enumerate(nums))

    The variables n and s are initialized to store the length of the array and the sum of its elements respectively. This is done to avoid recalculating these values in each iteration of the loop, which follows next.

    1n, s = len(nums), sum(nums)
  2. Initializing the Maximum Value: Before beginning the loop, we record the initial value of F(0) in the variable ans as this might be the maximum value.

    1ans = f
  3. Iterative Calculation of Subsequent F(k): We know that the subsequent value F(k) can be derived from F(k-1) by adding the sum of the array s to it and subtracting n times the last element of the array before it got rotated to the front, which is nums[n - i].

    The loop runs from 1 to n - 1 representing all possible k rotations (starting from 1 because we have already calculated F(0)).

    1for i in range(1, n):
    2    f = f + s - n * nums[n - i]
    3    ans = max(ans, f)
    • We adjust f to find the current F(k). The s is the total sum of the array, and we subtract the value that would have been added if there had been no rotation multiplied by n, which is n * nums[n - i]. We're subtracting it because its index in the function F effectively decreases by n due to the rotation.
    • We update ans with the maximum value found so far by comparing it with the newly computed F(k).
  4. Returning the Result: Once all rotations have been considered, the variable ans holds the maximum value found, which is then returned.

In terms of complexity, the time complexity of this solution is O(n) since it iterates through the array once after calculating the initial F(0). The space complexity is O(1) since it uses a fixed number of variables and doesn't allocate any additional data structures proportionate to the size of the input.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which algorithm should you use to find a node that is close to the root of the tree?

Example Walkthrough

Let's consider a small array nums = [4, 3, 2, 6] to illustrate the solution approach.

  1. Initial Value of F(0): We calculate F(0) by multiplying each element by its index and summing them up:

    F(0) = 0*4 + 1*3 + 2*2 + 3*6 = 0 + 3 + 4 + 18 = 25

    In the code, this is done using:

    1f = sum(i * v for i, v in enumerate(nums))

    We also compute the total sum of the array s = 4 + 3 + 2 + 6 = 15 and store the number of elements n = 4. These are calculated once to be used in subsequent rotation calculations:

    1n, s = len(nums), sum(nums)
  2. Initializing the Maximum Value: We start by considering F(0) as the potential maximum.

    1ans = f  # ans = 25 initially
  3. Iterative Calculation of Subsequent F(k): Now we calculate F(1) based on F(0):

    F(1) = F(0) + s - n * nums[n - 1]

    F(1) = 25 + 15 - 4*6 = 25 + 15 - 24 = 16

    And we check if this is greater than the current maximum ans:

    1ans = max(ans, f)  # ans remains 25 as 16 < 25

    Next, we calculate F(2):

    F(2) = F(1) + s - n * nums[n - 2] = 16 + 15 - 4*2 = 16 + 15 - 8 = 23

    Again, we update if it's greater than ans:

    1ans = max(ans, f)  # ans remains 25 as 23 < 25

    Finally, calculate F(3):

    F(3) = F(2) + s - n * nums[n - 3] = 23 + 15 - 4*3 = 23 + 15 - 12 = 26

    Now F(3) is greater than the current maximum ans, so we update ans:

    1ans = max(ans, f)  # ans is now updated to 26
  4. Returning the Result: We have considered all possible rotations (F(0) through F(3)) and the maximum value of F(k) is 26, achieved at k = 3. This is returned as the result.

    1return ans  # returns 26

Putting all this into action with our small example array nums = [4, 3, 2, 6], we find the rotation function that yields the highest value is F(3), and the maximum value returned is 26.

Solution Implementation

1class Solution:
2    def max_rotate_function(self, nums: List[int]) -> int:
3        # Calculate the initial value of the function F
4        total_function_value = sum(index * value for index, value in enumerate(nums))
5      
6        # Get the number of elements and the sum of all elements in nums
7        num_elements = len(nums)
8        sum_of_elements = sum(nums)
9
10        # Initialize ans with the initial total_function_value
11        max_function_value = total_function_value
12      
13        # Iterate through the array to find the maximal F value after rotations
14        for i in range(1, num_elements):
15            # Rotate the array by one element towards the right and update the function value
16            # This is achieved by adding the sum of all elements minus the last element value
17            # that is 'rotated' to the 'front' of the array times the number of elements
18            total_function_value += sum_of_elements - num_elements * nums[num_elements - i]
19          
20            # Update max_function_value if the new total_function_value is greater
21            max_function_value = max(max_function_value, total_function_value)
22      
23        # Return the maximum value found
24        return max_function_value
25
1class Solution {
2    public int maxRotateFunction(int[] nums) {
3        int firstComputation = 0;  // This will store the initial computation of the function F(0)
4        int sumOfAllNumbers = 0;   // This holds the sum of all the elements in the array
5        int n = nums.length;       // Total number of elements in the array
6        // Calculate the initial value of F(0) and sum of all numbers in the array
7        for (int i = 0; i < n; ++i) {
8            firstComputation += i * nums[i];
9            sumOfAllNumbers += nums[i];
10        }
11        int maxResult = firstComputation;  // Initialize maxResult with the first computation of the function
12      
13        // Compute the maximum value of F(i) by iterating through the possible rotations
14        for (int i = 1; i < n; ++i) {
15            // Compute the next value of F based on the previous value (F = F + sum - n * nums[n - i])
16            firstComputation = firstComputation + sumOfAllNumbers - n * nums[n - i];
17            // Update maxResult if the new computed value is greater than the current maxResult
18            maxResult = Math.max(maxResult, firstComputation);
19        }
20        // Return the maximum result found
21        return maxResult;
22    }
23}
24
1#include <vector>
2#include <algorithm> // For std::max
3
4class Solution {
5public:
6    int maxRotateFunction(std::vector<int>& nums) {
7        int currentFunctionValue = 0; // Initialize sum of i*nums[i]
8        int sumOfElements = 0; // Initialize sum of nums[i] for all i
9        int numberOfElements = nums.size(); // Number of elements in the array
10
11        // Calculate initial configuration values for currentFunctionValue and sumOfElements
12        for (int i = 0; i < numberOfElements; ++i) {
13            currentFunctionValue += i * nums[i];
14            sumOfElements += nums[i];
15        }
16      
17        int maxFunctionValue = currentFunctionValue; // Initialize the maximal value of F with current configuration
18      
19        // Iterate over the array to find the maximal rotation function value
20        for (int i = 1; i < numberOfElements; ++i) {
21            // Compute the next value of F by adding the sumOfElements and subtracting
22            // the last element multiplied by the number of elements
23            currentFunctionValue = currentFunctionValue + sumOfElements - numberOfElements * nums[numberOfElements - i];
24          
25            // Update the maxFunctionValue with the maximum of current and the newly computed value
26            maxFunctionValue = std::max(maxFunctionValue, currentFunctionValue);
27        }
28
29        // Return the maximum value found for the rotation function
30        return maxFunctionValue;
31    }
32};
33
1function maxRotateFunction(nums: number[]): number {
2    const numElements = nums.length; // The number of elements in the input array
3  
4    // Calculate the sum of all numbers in the array
5    const totalSum = nums.reduce((accumulator, value) => accumulator + value, 0);
6  
7    // Initialize the function result using the formula F(0) = 0 * nums[0] + 1 * nums[1] + ... + (n-1) * nums[n-1]
8    let maxFunctionValue = nums.reduce((accumulator, value, index) => accumulator + value * index, 0);
9  
10    // The previous state's function value, starting with F(0)
11    let previousFunctionValue = maxFunctionValue;
12  
13    // Iterate through the array to find the maximum function value after each rotation
14    for (let i = 1; i < numElements; i++) {
15        // Calculate the function value F(i) for the current rotation based on F(i-1), the previous rotation
16        previousFunctionValue = previousFunctionValue - (totalSum - nums[i - 1]) + nums[i - 1] * (numElements - 1);
17        // Update the maximum function value found so far
18        maxFunctionValue = Math.max(maxFunctionValue, previousFunctionValue);
19    }
20  
21    // Return the maximum found function value
22    return maxFunctionValue;
23}
24
Not Sure What to Study? Take the 2-min Quiz:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the nums list. This is because there is one initial loop that goes through the numbers in nums to calculate the initial value of f, which will take O(n) time. After that, there is a for-loop that iterates n-1 times, and in each iteration, it performs a constant amount of work which does not depend on n. Hence, the loop contributes O(n) to the time complexity as well.

The space complexity of the code is O(1). This is because only a constant amount of extra space is used for variables f, n, s, and ans, and the input nums is not being copied or expanded, thus the space used does not grow with the size of the input.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

How does quick sort divide the problem into subproblems?


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫