Smallest Rotation With Highest Score


It seems that this is not a "Interval Stabbing" problem
https://www.cs.cmu.edu/afs/cs/academic/class/15210f11/www/resources/recis/rec12.pdf
Please correct me if I am wrong.

Can anyone please explain:
"what we will do instead is keep track of the cumulative total: bad[2]; bad[5]++. For "wraparound" intervals like [8, 9, 0, 1, 2], we will keep track of this as two separate intervals: bad[8], bad[10]++, bad[0], bad[3]++. (Actually, because of our implementation, we don't need to remember the bad[10]++ part.)"It totally went over my head.

@Aakash_Ajay Hi I think i figure this out. It's tricky but brilliant. Let's say you have an array bad with index from 0 to 5. bad[2], bad[3], bad[4], makes the array looks like this:
So the 1 give an information that there is an interval [2,3,4]. To save time instead of this you will do bad[2] and bad[5]++ which result in:
and then you do a cumulative sum from i = 1 to end of array bad[i] += bad[i1]:
.
It will be still beter time because the idea is that you put all the bad[left] and bad[right] first and then at the end make cumulative sum once. Small example: two intervals [1,2,3]; [3,4]:

Hi there, I think there is a mistake in the explanation :
When we shift by 2, we'll get final index 0. ==> ok If we shift 51 = 4 before this, this element will end up at final index 4. ==> seems wrong, we end up at index 6 !
I think you meant that if we shift by 8, we end up at position 4

@bodziozet ya, I got your explanation, the logic is so elegant, it took time to digest in.

public int bestRotation(int[] a) { int[] resultArray = new int[a.length]; int finalScore = 0; for (int m = 0; m <= a.length  1; m++) { Integer new_index = 0; for (int i = 0; i <= a.length  1; i++) { if ((i  a[m]) < 0) { new_index = (i  a[m]) + (a.length); } else { new_index = (i  a[m]); } resultArray[new_index] = a[i]; } int totalscore = 0; for (int j = 0; j <= resultArray.length  1; j++) { if (resultArray[j] <= j) { totalscore++; } } if (totalscore > finalScore) { finalScore = totalscore; } } return finalScore; }