Short and Simple Python O(n) time O(1) space


  • 0

    Start by getting the rotation function at k = 0 and the sum of the entire array. We can observe that every unit of rotation is = previous sum - sum of the array except item at i + max_index of array * item at i. This is because each rotation decrements the multiplier for all items to the right of position i (which is the previous iteration's position where the multiplier 0 is) by 1 while setting the multiplier for the item at position i to the max index of the array. Thus we can use the sum of the previous iteration(rotation) and the relative changes to calculate the new sum for the current rotation.

        def maxRotateFunction(self, A):
            arr_sum = sum(A)  # sum of all elems
            mx = s = sum(i * A[i] for i in range(len(A))) # rotation function at k = 0
            # don't have to do for last item as the sum for that iteration is what we're starting with
            for i in range(len(A)-1): 
                s += len(A)*A[i] - arr_sum  
                mx = max(mx, s)
            return mx
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.