O(nlogn) more basic approach: max overlapping intervals problem
We know that each element in the array has at most 2 intervals for k on which it scores a point. Therefore, we can\nfind these intervals and compute the maximum
We know that each element in the array has at most 2 intervals for k on which it scores a point. Therefore, we can\nfind these intervals and compute the maximum overlap between them. Although this isn\'t the Ideal solution that is \npresented in the posts, it\'s what came to mind for me at first so here is the code. We could probably transform this to the O(n)\nby using a hashmap of events instead of sorting. \n```\n    int bestRotation(vector<int>& A) {\n        /*\n            A[i], k, n score = 1 : A[i] <= (i - k + n) % n\n            \n        */\n        int n = A.size();\n        vector<vector<int>> intervals;\n        int minidx;\n        int maxidx;\n        for (int i = 0; i < n; ++i) {\n            if (A[i] == n) continue;\n            minidx = A[i];\n            maxidx = n - 1;\n            if (i < minidx) {\n                intervals.push_back({i + 1, 1});\n                intervals.push_back({i + 1 + maxidx - minidx, -1});\n            } else {\n                intervals.push_back({0, 1});\n                intervals.push_back({i - minidx, -1});\n                if (i != n - 1) { \n                    intervals.push_back({i + 1, 1});\n                    intervals.push_back({n - 1, -1});\n                }\n            }\n        }\n        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) -> bool {\n            return a[0] < b[0] || (a[0] == b[0] && a[1] > b[1]);\n        });\n        int ans = 0;\n        int laps = 0;\n        int mlaps = INT_MIN;\n        for (const auto& p : intervals) {\n            if (p[1] == 1) {\n                ++laps;\n                if (laps > mlaps) {\n                    mlaps = laps;\n                    ans = p[0];\n                }\n            } else {\n                --laps;\n            }\n        }\n        return ans;\n    }\n```
[]