wow
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nimport java.util.*;\n\nclass Solution {\n\n    // rotations that make sense: 0..K - 1 since K = 0 rotation\n    // each index -> (K - 1) other possible indexes\n    // max score = N\n    // slide K means K -> 0; K + 1 -> 1...\n\n    // IDEALLY, A[i] = M MUST be in range 0...M]\n    // Given A[i] = M is in the range 0...M:\n    // 0 rotations, stays INSIDE; +1 score\n    // any P rotations, goes OUTSIDE; -1 score\n    // any Q rotations, stays INSIDE; +1 score\n\n    // BUILD DIFF ARRAY ON number of rotations K: instead of looping over each\n    // mark them based on INTERVALS:  A[i] <= i\n    // Given A[i] = M is in the range 0...M:\n    // min_rotation to keep in range = 0\n    // max_rotation to keep in range = i - A[i]\n\n    // diff[0] += 1                       0 rotations, stays INSIDE; +1 score\n    // diff[min_rotation] += 1            stays INSIDE; +1 score\n    // diff[max_rotation + 1] -= 1        goes OUTSIDE; -1 score\n\n    // Given A[i] = M is OUTSIDE range 0...M:\n    // min_rotation to GET in range  = i + 1; brings it to position (N-1)\n    // max_rotation to keep in range = min_rotation + (N - 1) - A[i]\n\n    // diff[0] -= 1                       0 rotations, stays OUTSIDE; -1 score\n    // diff[min_rotation] += 1            stays INSIDE; +1 score\n    // diff[max_rotation + 1] -= 1        goes OUTSIDE; -1 score\n\n    // finally we process diff[] and find which K is best\n\n//   [2,3,1,4,0] ORIGINAL ARRAY\n// 2:[_,x,x,x,_]  x = num rotations works for this number\n// 3:[_,_,x,x,_]\n// 1:[x,x,_,x,x]        // EDGE CASE!!!!!!!!!!!!!\n// 4:[_,_,_,_,x]\n// 0:[x,x,x,x,x]\n//   [0,1,2,3,4] NUM ROTATIONS\n//          X - 4 overlapping; at K = 3\n\n//    A[i] = 2 from: 1 to: 3\n//    A[i] = 3 from: 2 to: 3\n//    A[i] = 1 from: 0 to: 1\n//    A[i] = 4 from: 4 to: 4\n//    A[i] = 0 from: 0 to: 4\n//            [0, 1, -1, 1, -1]\n    public int bestRotation(int[] A) {\n        int n = A.length;\n        int[] diff = new int[n]; // N rotations = 0; use MOD!!!\n\n        for (int i = 0; i < n; i++) {\n            if (A[i] <= i) { // in range\n                // check all possible left places as an interval\n                int minRot = 0;\n                int maxRot = i - A[i];\n                diff[minRot]++;\n                diff[(maxRot + 1) % n]--;\n\n                // BUT might also be able to loop it on the right side;  SEE  // EDGE CASE!!!!!!!!!!!!!\n                int minRotLoop = i + 1;\n                int maxRotLoop = minRotLoop + (n - 1) - A[i];\n                diff[minRotLoop % n]++;\n                if (maxRotLoop + 1 < n) diff[(maxRotLoop + 1) % n]--;\n            } else { // outside range; need to loop it on the right side\n                int minRot = i + 1;\n                int maxRot = minRot + (n - 1) - A[i];\n                diff[minRot % n]++;\n                diff[(maxRot + 1) % n]--;\n            }\n        }\n        int best = 0, bestK = 0, curr = 0;\n        for (int k = 0; k < n; k++) {\n            curr += diff[k];\n            if (curr > best) {\n                bestK = k;\n                best = curr;\n            } else if (best == curr && k < bestK) {\n                bestK = k;\n            }\n        }\n        return bestK;\n    }\n\n}\n\n```
['Java']