798. Smallest Rotation with Highest Score
IntuitionApproachComplexity
Time complexity:

Space complexity:
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
public:
    int bestRotation(vector<int>& nums) {
        int size = nums.size();
        vector<int> rotationImpact(2 * size + 1, 0);
        
        for (int i = 0; i < size; i++) {
            int lower = 0, upper = 0;
            if (nums[i] <= i) {
                lower = 0;
                upper = i - nums[i];
                rotationImpact[lower] += 1;
                rotationImpact[upper + 1] -= 1;
            }
            lower = i + 1;
            upper = i + size - nums[i];
            rotationImpact[lower] += 1;
            rotationImpact[upper + 1] -= 1;
        }

        int maxRotation = rotationImpact[0], optimalIndex = 0;
        for (int i = 1; i < rotationImpact.size(); i++) {
            rotationImpact[i] += rotationImpact[i - 1];
            if (rotationImpact[i] > maxRotation) {
                maxRotation = rotationImpact[i];
                optimalIndex = i;
            }
        }
        
        return optimalIndex;
    }
};

```
['C++']