Approach #1: Interval Stabbing [Accepted]
N = 10 and
A = 5. Then there are 5 rotations that are bad for this number: rotation indexes
0, 1, 2, 8, 9 - these rotations will cause this number to not get 1 point later.
In general, for each number in the array, we can map out what rotation indexes will be bad for this number. It will always be a region of one interval, possibly two if the interval wraps around (eg.
8, 9, 0, 1, 2 wraps around, to become
[8, 9] and
[0, 1, 2].)
At the end of plotting these intervals, we need to know which rotation index has the least intervals overlapping it - this one is the answer.
First, an element like
A = 5 will not get score in (up to) 5 posiitons: when the 5 is at final index 0, 1, 2, 3, or 4. When we shift by 2, we'll get final index 0. If we shift
5-1 = 4 before this, this element will end up at final index 4. In general (modulo N), a shift of
i - A[i] + 1 to
i will be the rotation indexes that will make
A[i] not score a point.
If we are trying to plot an interval like
[2, 3, 4], then instead of doing
bad--; bad--; bad--;, what we will do instead is keep track of the cumulative total:
bad--; bad++. For "wrap-around" intervals like
[8, 9, 0, 1, 2], we will keep track of this as two separate intervals:
bad--, bad++, bad--, bad++. (Actually, because of our implementation, we don't need to remember the
At the end, we want to find a rotation index with the least intervals overlapping. We'll maintain a cumulative total
cur representing how many intervals are currently overlapping our current rotation index, then update it as we step through each rotation index.
Time Complexity: , where is the length of
Space Complexity: .
Analysis written by: @awice.