Sliding window + prefix sum solution O(n) | Java
\nclass Solution {\n    /*\n        1. let\'s assume we have an array with 2 * n size\n            from [2,3,1,4,0] to [2,3,1,4,0,2,3,1,4,0]\n        2. loop th
```\nclass Solution {\n    /*\n        1. let\'s assume we have an array with 2 * n size\n            from [2,3,1,4,0] to [2,3,1,4,0,2,3,1,4,0]\n        2. loop through every element from left to right\n            index 0 1 2 3 4 5 6 7 8 9\n                 [2,3,1,4,0,2,3,1,4,0]\n        3. we can find the different value between index and element, we only keep value >= 0\n            index 0 1 2 3 4 5 6 7 8 9\n                 [2,3,1,4,0,2,3,1,4,0]\n            value     1   4 3 3 6 4 9\n        4. we perform sliding window(size n) on this pattern\n            l = left pointer of window, r = current right pointer\n            index 0 1 2 3 4 5 6 7 8 9\n                 [2,3,1,4,0,2,3,1,4,0]\n            value     1   4 3 3 6 4 9 : if left pointer pass this value, this value cannot be counted in result\n                  l       r\n            value : if left pointer smaller than or equal to 1, we can keep it in window\n                    (largest left pointer index to keep this element in our window)\n        5. we use variable "sum" to keep tracking current count of valid elements\n            but we need to remove invalid value from "sum"\n        6. in order to remove invalid left pointer / value, we need count[] array to mark element count at that index\n            before moving left pointer point to next index, we need to use sum - count[left]\n   example   \n            index 0 1 2 3 4 5 6 7 8 9\n                 [2,3,1,4,0,2,3,1,4,0]\n            value     1   4 3 3 6 4 9\n    left = 0, right = 2, sum = 1, count = {{1:1}}\n    left = 0, right = 4, sum = 2, count = {{1:1}, {4:1}}\n    left = 1, right = 5, sum = 3, count = {{1:1}, {4:1}, {3:1}}\n        after calculate max / possible result, we need to remove count[left] from sum\n    left = 1, right = 5, sum = (3 - count[left]) = 2, count = {{1:1}, {4:1}, {3:1}}\n    left = 2, right = 6, sum = 3, count = {{1:1}, {4:1}, {3:2}}\n    left = 3, right = 7, sum = 4, count = {{1:1}, {4:1}, {3:2}, {6:1}}\n        after calculate max / possible result, we need to remove count[left] from sum\n    left = 3, right = 7, sum = (4 - count[left]) = 2, count = {{1:1}, {4:1}, {3:2}, {6:1}}\n    left = 4, right = 8, sum = 3, count = {{1:1}, {4:2}, {3:2}, {6:1}}\n        after calculate max / possible result, we need to remove count[left] from sum\n    left = 4, right = 8, sum = (3 - count[left]) = 1, count = {{1:1}, {4:2}, {3:2}, {6:1}}    \n    ....\n    \n    \n    */\n    public int bestRotation(int[] nums) {\n        int n = nums.length;\n        int[] cnt = new int[2 * n];\n        int max = 0;\n        int res = 0;\n        for(int r = 0, l = 0, sum = 0; r < 2 * n; r++) {\n            int v = r - nums[r % n];\n            if(v >= 0) {\n                cnt[Math.min(2 * n - 1, v)]++;\n                if(v >= l) {\n                    sum++;\n                }\n            }\n            if(r - l == n - 1) {\n                if(sum > max) {\n                    max = sum;\n                    res = l;\n                }\n                sum -= cnt[l];\n                l++;\n            }\n        }\n        return res;\n    }\n}\n```
['Sliding Window', 'Java']