Leetcode 396. Rotate Function

Problem Explanation

The main task of this problem is to figure out the maximum value that can be obtained by rotating an array of integers in a given function. Assume that there is an array 'A' and 'n' is the length of the array. After rotating the array 'A' k positions clock-wise, we get another array 'Bk'. The rotation function 'F' is defined as F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1]. We need to calculate the maximum value of F(0), F(1), ..., F(n-1).

If we look at the function itself, we can observe that each rotation will shift all numbers right by one position. Therefore, the sum of products of number and index will be sum + n*Bk[0]. We need to calculate the rotation function for each possible rotation and keep track of the maximum one.

Solution Approach

The basic idea of the solution is to find a relationship between each round of rotation to accumulate the result for each round by only adding the difference between each round.

First, we calculate the total sum and the initial rotation function. Then, for each new rotation, we update the rotation function by adding the total sum of the array and subtracting the size of the array times the element that gets out of the array after the rotation. We keep track of the maximum rotation function value.

In other words, after rotating, every number contributes its value to the new result. However, the number that is kicked out of the array will not contribute its value, but will decrease the total sum times its count, times array length. Therefore, each time we rotate, we just add the whole sum, but deduct "size times the last element" from it.

Let's go through an example: Suppose we have an array [4, 3, 2, 6] F(0) = (04) + (13) + (22) + (36) = 25 To calculate F(1), we will add total sum to F(0) and then subtract the product of last element and size of array.

That will be F(1) = F(0) + sum([4,3,2,6]) - 4*6 = 25 + 15 - 24 = 16 Similarly, we calculate F(2) and F(3) to find the maximum from all rotations which in this case would be 26.

1
2 python
3class Solution:
4  def maxRotateFunction(self, nums):
5    total = sum(nums)
6    rotation_function = sum(i * nums[i] for i in range(len(nums)))
7    max_value = rotation_function
8    for i in range(1, len(nums)):
9      rotation_function += total - len(nums) * nums[-i]
10      max_value = max(max_value, rotation_function)
11    return max_value

Python Solution

1
2 python
3class Solution:
4  def maxRotateFunction(self, nums):
5    total = sum(nums)
6    rotation_function = sum(i * nums[i] for i in range(len(nums)))
7    max_value = rotation_function
8    for i in range(1, len(nums)):
9      rotation_function += total - len(nums) * nums[-i]
10      max_value = max(max_value, rotation_function)
11    return max_value

Java Solution

1
2 java
3class Solution {
4  public int maxRotateFunction(int[] nums) {
5    int sum = 0, rotation = 0;
6    for (int i = 0; i < nums.length; i++) {
7      sum += nums[i];
8      rotation += i * nums[i];
9    }
10    int max_value = rotation;
11    for (int i = 1; i < nums.length; i++) {
12      rotation += sum - nums.length * nums[nums.length - i];
13      max_value = Math.max(max_value, rotation);
14    }
15    return max_value;
16  }
17}

Javascript Solution

1
2 javascript
3class Solution {
4  maxRotateFunction(nums) {
5    let sum = 0, rotation = 0;
6    for (let i = 0; i < nums.length; i++) {
7      sum += nums[i];
8      rotation += i * nums[i];
9    }
10    let max_value = rotation;
11    for (let i = 1; i < nums.length; i++) {
12      rotation += sum - nums.length * nums[nums.length - i];
13      max_value = Math.max(max_value, rotation);
14    }
15    return max_value;
16  }
17}

C++ Solution

1
2 c++
3class Solution {
4public:
5    int maxRotateFunction(vector<int>& nums) {
6        int sum = 0, rotation = 0;
7        for (int i = 0; i < nums.size(); i++) {
8            sum += nums[i];
9            rotation += i * nums[i];
10        }
11        int max_value = rotation;
12        for (int i = 1; i < nums.size(); i++) {
13            rotation += sum - nums.size() * nums[nums.size() - i];
14            max_value = max(max_value, rotation);
15        }
16        return max_value;
17    }
18};

C# Solution

1
2 csharp
3public class Solution {
4  public int MaxRotateFunction(int[] nums) {
5    int sum = 0, rotation = 0;
6    for (int i = 0; i < nums.Length; i++) {
7      sum += nums[i];
8      rotation += i * nums[i];
9    }
10    int max_value = rotation;
11    for (int i = 1; i < nums.Length; i++) {
12      rotation += sum - nums.Length * nums[nums.Length - i];
13      max_value = Math.Max(max_value, rotation);
14    }
15    return max_value;
16  }
17}

Ruby Solution

1
2 ruby
3class Solution
4  def max_rotate_function(nums)
5    total = nums.sum()
6    rotation = 0
7    for i in 0...nums.length()
8      rotation += i * nums[i]
9    end
10    max_value = rotation
11    for i in 1...nums.length()
12      rotation += total - nums.length() * nums[-i]
13      max_value = [max_value, rotation].max()
14    end
15    return max_value
16  end
17end

Swift Solution

1
2 swift
3class Solution {
4    func maxRotateFunction(_ nums: [Int]) -> Int {
5        let total = nums.reduce(0, +)
6        var rotation = 0
7        for i in 0..<nums.count {
8            rotation += i*nums[i]
9        }
10        var max_value = rotation
11        for i in 1..<nums.count {
12            rotation += total - nums.count * nums[nums.count - i]
13            max_value = max(max_value, rotation)
14        }
15        return max_value
16    }
17}

Kotlin Solution

1
2 kotlin
3class Solution {
4    fun maxRotateFunction(nums: IntArray): Int {
5        var total = 0
6        var rotation = 0
7        for (i in nums.indices) {
8            total += nums[i]
9            rotation += i * nums[i]
10        }
11        var max_value = rotation
12        for (i in 1 until nums.size) {
13            rotation += total - nums.size * nums[nums.size - i]
14            max_value = max_value.coerceAtLeast(rotation)
15        }
16        return max_value
17    }
18}

In conclusion, this problem is a good example of how to optimize a brute force solution by identifying patterns or relationships between sub-problems. The key is to understand the rotation operation and its effects on the array and the given function. This enhances algorithmic thinking and helps in solving problems more efficiently.