We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Rotate Function

Number: 396

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given an integer array nums, define the rotation function F for an array rotation arrₖ (rotating nums by k clockwise) as:
F(k) = 0 * arrₖ[0] + 1 * arrₖ[1] + ... + (n - 1) * arrₖ[n - 1].
The goal is to compute and return the maximum value among F(0), F(1), ..., F(n-1).

Key Insights

  • Calculate the total sum S of the array and the initial function value F(0).
  • Derive the recurrence: F(k+1) = F(k) + S - n * element_moved, where element_moved is the element that transitions from the end to the front.
  • This recurrence helps compute F for each rotation in O(n) time, avoiding an O(n²) recalculation.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

We start by computing the sum of all elements (S) and F(0) by summing i*nums[i] for all indices. To derive F(k+1) from F(k), observe that when the array is rotated, each element's contribution increases by its value (total S), while the element shifted from the end to the front loses its original weighted contribution (n times its value). This observation forms the recurrence relation, allowing us to update the function value in O(1) time per rotation and track the maximum value.

Code Solutions

# Python solution with detailed line-by-line comments

def maxRotateFunction(nums):
    # Compute the total sum of the array elements
    total_sum = sum(nums)
    n = len(nums)
    
    # Compute the initial rotation function F(0)
    current_F = 0
    for i in range(n):
        current_F += i * nums[i]
    
    # Initialize max_F with the value of F(0)
    max_F = current_F
    
    # Iterate over each rotation k from 1 to n-1
    for k in range(1, n):
        # Update F(k) using the relationship:
        # F(k) = F(k-1) + total_sum - n * nums[n - k]
        current_F = current_F + total_sum - n * nums[n - k]
        # Update max_F if the current rotation function is greater
        max_F = max(max_F, current_F)
    
    return max_F

# Example usage
if __name__ == "__main__":
    nums = [4, 3, 2, 6]
    print(maxRotateFunction(nums))  # Expected output: 26
← Back to All Questions