LeetCode 396: Rotate Function Solution in Python – A Step-by-Step Guide

Imagine you’re given an array—like [4, 3, 2, 6]—and you need to compute a function F(k) for each rotation of the array, where F(k) = 0 * arr[0] + 1 * arr[1] + ... + (n-1) * arr[n-1], then find the maximum value across all rotations. That’s the challenge of LeetCode 396: Rotate Function, a medium-level problem that’s all about array rotation and optimization. Using Python, we’ll explore two solutions: the Best Solution—mathematical optimization for O(n) efficiency—and an Alternative Solution—brute force simulation at O(n²). With examples, clear code breakdowns, and a friendly vibe, this guide will help you maximize that function. Let’s start rotating!

What Is LeetCode 396: Rotate Function?

Section link icon

LeetCode 396: Rotate Function provides an integer array nums, and defines a function F(k) for the k-th rotation of the array as F(k) = 0 * nums[0] + 1 * nums[1] + ... + (n-1) * nums[n-1]. Your task is to return the maximum value of F(k) over all possible rotations (k = 0 to n-1). It’s a problem that tests your ability to optimize a repetitive computation efficiently!

Problem Statement

  • Input:
    • nums: List of integers.
  • Output: Integer - Maximum value of F(k) across all rotations.
  • Rules:
    • F(k) = sum of i * nums[i] for i from 0 to n-1 after k right rotations.
    • Rotation shifts elements right, wrapping last to front (e.g., [1,2,3] → [3,1,2]).
    • Compute max F(k) for k = 0 to n-1.

Constraints

  • n == nums.length
  • 1 <= n <= 10⁵
  • -100 <= nums[i] <= 100

Examples

  • Input: nums = [4,3,2,6]
    • Output: 26
      • F(0) = 0*4 + 1*3 + 2*2 + 3*6 = 25.
      • F(1) = 0*6 + 1*4 + 2*3 + 3*2 = 16.
      • F(2) = 0*2 + 1*6 + 2*4 + 3*3 = 23.
      • F(3) = 0*3 + 1*2 + 2*6 + 3*4 = 26.
      • Max = 26.
  • Input: nums = [100]
    • Output: 0
      • F(0) = 0*100 = 0, only one rotation.
  • Input: nums = [-1,-2]
    • Output: -1
      • F(0) = 0*-1 + 1*-2 = -2.
      • F(1) = 0*-2 + 1*-1 = -1.
      • Max = -1.

These show the rotation game—let’s solve it!

Understanding the Problem: Maximizing the Rotate Function

Section link icon

To tackle LeetCode 396 in Python, we need to: 1. Compute F(k) for each rotation k = 0 to n-1. 2. Find the maximum value efficiently. 3. Handle arrays up to 10⁵ elements.

A naive approach might compute F(k) for each rotation separately, but that’s O(n²). We’ll use:

  • Best Solution: Mathematical optimization—O(n) time, O(1) space—fast and optimal.
  • Alternative Solution: Brute force simulation—O(n²) time, O(n) space—intuitive but slow.

Let’s optimize with the best solution!

Best Solution: Mathematical Optimization

Section link icon

Why This Is the Best Solution

The mathematical optimization approach runs in O(n) time with O(1) space by deriving a recurrence relation between consecutive F(k) values, computing each in O(1) after an initial O(n) setup. It’s the most efficient—leveraging the pattern of rotation to avoid recomputing sums, making it ideal for large n!

How It Works

Think of it like a rotating wheel:

  • F(k) Definition: F(k) = 0 * nums[0] + 1 * nums[1] + ... + (n-1) * nums[n-1] after k rotations.
  • Pattern:
    • Rotating right shifts indices: F(k+1) reuses F(k) but adjusts weights.
    • F(k+1) = F(k) + sum(nums) - n * nums[n-1-k].
  • Process:
    • Compute initial F(0) and array sum.
    • Iterate k, update F(k) using recurrence.
    • Track maximum.
  • Result: Max F(k) over all rotations.

It’s like spinning the array with math!

Step-by-Step Example

For nums = [4,3,2,6]:

  • Init:
    • n = 4, sum_nums = 4 + 3 + 2 + 6 = 15.
    • F(0) = 0*4 + 1*3 + 2*2 + 3*6 = 0 + 3 + 4 + 18 = 25.
  • k=1:
    • F(1) = F(0) + sum_nums - n * nums[n-1] = 25 + 15 - 4*6 = 25 + 15 - 24 = 16.
  • k=2:
    • F(2) = F(1) + sum_nums - n * nums[n-2] = 16 + 15 - 4*2 = 16 + 15 - 8 = 23.
  • k=3:
    • F(3) = F(2) + sum_nums - n * nums[n-3] = 23 + 15 - 4*3 = 23 + 15 - 12 = 26.
  • Result: max(25, 16, 23, 26) = 26.

For nums = [100]:

  • F(0): 0 * 100 = 0, sum = 100, no further rotations.
  • Result: 0.

Code with Explanation

Here’s the Python code using mathematical optimization:

class Solution:
    def maxRotateFunction(self, nums: List[int]) -> int:
        # Array length and sum
        n = len(nums)
        sum_nums = sum(nums)

        # Compute F(0)
        f = 0
        for i in range(n):
            f += i * nums[i]

        # Track maximum and compute F(k) iteratively
        max_f = f
        for i in range(1, n):
            # F(k) = F(k-1) + sum - n * nums[n-1-(k-1)]
            f = f + sum_nums - n * nums[n - i]
            max_f = max(max_f, f)

        return max_f

Explanation

  • Lines 4-5: n: Array length, sum_nums: Sum of nums—O(n).
  • Lines 7-9: Compute F(0)—O(n).
  • Lines 11-15: Iterate rotations:
    • Update F(k) using recurrence—O(1).
    • Track max—O(1).
  • Line 17: Return maximum—O(1).
  • Time: O(n)—single pass for sum and F(0), then O(n) iterations.
  • Space: O(1)—few variables.

This is like a rotation calculator—fast and sleek!

Alternative Solution: Brute Force Simulation

Section link icon

Why an Alternative Approach?

The brute force simulation solution runs in O(n²) time with O(n) space by explicitly computing F(k) for each rotation by rotating the array and summing products. It’s intuitive—great for small n or understanding the process, but impractical for large n due to time complexity!

How It Works

  • Rotate: Simulate each rotation.
  • Compute: Calculate F(k) = sum(i * nums[i]).
  • Track: Max F(k) over all rotations.
  • Result: Return maximum.

Step-by-Step Example

For nums = [4,3,2,6]:

  • k=0: [4,3,2,6], F(0) = 0*4 + 1*3 + 2*2 + 3*6 = 25.
  • k=1: [6,4,3,2], F(1) = 0*6 + 1*4 + 2*3 + 3*2 = 16.
  • k=2: [2,6,4,3], F(2) = 0*2 + 1*6 + 2*4 + 3*3 = 23.
  • k=3: [3,2,6,4], F(3) = 0*3 + 1*2 + 2*6 + 3*4 = 26.
  • Result: max(25, 16, 23, 26) = 26.

Code with Explanation

class Solution:
    def maxRotateFunction(self, nums: List[int]) -> int:
        n = len(nums)
        max_f = float('-inf')

        # Try each rotation
        for k in range(n):
            rotated = nums[n-k:] + nums[:n-k]  # Rotate array
            f = 0
            for i in range(n):
                f += i * rotated[i]
            max_f = max(max_f, f)

        return max_f

Explanation

  • Line 4: max_f: Track maximum—O(1).
  • Lines 6-11: For each k:
    • Rotate array—O(n).
    • Compute F(k)—O(n).
    • Update max—O(1).
  • Line 13: Return max—O(1).
  • Time: O(n²)—n rotations, O(n) per rotation.
  • Space: O(n)—rotated array.

It’s a rotation simulator—clear but slow!

Comparing the Two Solutions

Section link icon
  • Mathematical Optimization (Best):
    • Time: O(n)—linear.
    • Space: O(1)—minimal.
    • Pros: Fast, space-efficient, scalable.
    • Cons: Requires pattern insight.
  • Brute Force Simulation (Alternative):
    • Time: O(n²)—quadratic.
    • Space: O(n)—array.
    • Pros: Easy to understand.
    • Cons: Slow, memory-heavy.

Math optimization wins for speed and efficiency!

Additional Examples and Edge Cases

Section link icon
  • [1]: Both return 0.
  • [-1,-2]: Both return -1.
  • Large n: Math scales, simulation lags.

Math is optimal, simulation works for small n.

Complexity Breakdown

Section link icon
  • Math Optimization:
    • Time: O(n).
    • Space: O(1).
  • Brute Force:
    • Time: O(n²).
    • Space: O(n).

Math excels for performance.

Key Takeaways

Section link icon
  • Math Optimization: Pattern power—fast and lean!
  • Brute Force: Simulate all—clear but slow!
  • Rotation: Math beats loops.
  • Python Tip: Logic rocks—see [Python Basics](/python/basics).

Final Thoughts: Maximize That Function

Section link icon

LeetCode 396: Rotate Function in Python is an optimization challenge. Mathematical optimization is the efficiency champ, while brute force offers a tangible alternative for small cases. Want more? Try LeetCode 48: Rotate Image or LeetCode 189: Rotate Array. Ready to rotate? Visit Solve LeetCode 396 on LeetCode and find that max today!