MediumNo. 0396
Rotate Function — LeetCode 396 Python Solution
- Pattern
- Dynamic Programming
- Topics
- Array, Math, Dynamic Programming
- Reading time
- 2 min
- Source
- leetcode.com
The problem
You are given an integer array nums of length n. Assume arrk to be an array obtained by rotating nums by k positions clock-wise.
Example
- Input
- nums = [4,3,2,6]
- Output
- 26
- Explanation
- F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
Python solution
class Solution:
def maxRotateFunction(self, nums: List[int]) -> int:
f = sum(i * v for i, v in enumerate(nums))
n, s = len(nums), sum(nums)
ans = f
for i in range(1, n):
f = f + s - n * nums[n - i]
ans = max(ans, f)
return ansComplexity
- Time
- O(n·m) (typical)
- Space · auxiliary
- O(n·m)or optimized
Pattern: Dynamic Programming
Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 396. Rotate Function is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.
The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0313 | Super Ugly Number | Medium |
| 0368 | Largest Divisible Subset | Medium |
| 0486 | Predict the Winner | Medium |
| 0553 | Optimal Division | Medium |
| 0805 | Split Array With Same Average | Hard |
| 0877 | Stone Game | Medium |
Frequently asked questions
- How hard is LeetCode 396. Rotate Function?
LeetCode 396. Rotate Function is rated Medium on LeetCode.
- What topics does LeetCode 396. Rotate Function cover?
LeetCode 396. Rotate Function is tagged Array, Math and Dynamic Programming on LeetCode.