Problem Statement in English

You’re given an array of integers nums. You have to calculate the maximum value of the function F(k), where F(k) is defined as:

$$ F(k) = 0 \cdot \text{nums}[k] + 1 \cdot \text{nums}[k+1] + \ldots + (n-1) \cdot \text{nums}[k+n-1] $$

where the array is considered to be rotated $k$ times clockwise.

Return the maximum value of F(k) for k = 0, 1, 2, ..., n-1.

Approach

Let’s look at the difference between two consecutive rotation functions. Suppose $k = 0$ and $k = 1$, and our array is $[a, b, c, d]$.

  • $F(0) = 0 \cdot a + 1 \cdot b + 2 \cdot c + 3 \cdot d$
  • $F(1) = 0 \cdot d + 1 \cdot a + 2 \cdot b + 3 \cdot c$

Now, let’s subtract $F(0)$ from $F(1)$:

$$F(1) - F(0) = (1a - 0a) + (2b - 1b) + (3c - 2c) + (0d - 3d)$$

$$F(1) - F(0) = a + b + c - 3d$$

We can rewrite this using the sum of all elements ($S = a + b + c + d$):

$$F(1) - F(0) = (a + b + c + d) - 4d$$

$$F(1) = F(0) + S - n \cdot \text{nums}[n-1]$$

In general, for any rotation $k$:

$$F(k) = F(k-1) + S - n \cdot \text{nums}[n-k]$$

where $\text{nums}[n-k]$ is the element that was at the end in the previous rotation. This gives us a $O(n)$ solution instead of computing each $F(k)$ independently in $O(n^2)$ time.

So using this we can calculate $F(1)$ from $F(0)$, then $F(2)$ from $F(1)$, and so on, while keeping track of the maximum value.

And we’re done!

Solution in Python


class Solution:
    def maxRotateFunction(self, nums):
        n = len(nums)
        total_sum = sum(nums)
        
        # Compute initial F(0)
        current_f = 0
        for i in range(n):
            current_f += i * nums[i]
        
        max_f = current_f
        
        # Compute F(1) through F(n-1) using the transition formula:
        # F(k) = F(k-1) + sum - n * nums[n-k]
        for k in range(1, n):
            # nums[n-k] is the element that was at the end in the previous rotation
            current_f = current_f + total_sum - n * nums[n - k]
            if current_f > max_f:
                max_f = current_f
                
        return max_f

Complexity

  • Time: $O(n)$

  • Space: $O(1)$
    Since we are using only a constant amount of extra space.

Mistakes I Made

I had to look this up :(

And we are done.