Difference Arrays

Posted on Edited on In Waline:

This week’s question of the day has a difficult level question, using a technique called difference array. This technique is actually not complicated, that is, the reverse operation of prefix and, simply record it.

Here is the link to the title: https://leetcode-cn.com/problems/smallest-rotation-with-highest-score/

The simplest way to do this problem is to iterate over each possible k, then calculate the score of the current array, and finally compare the score that is the largest in that case. If there are multiple largest, then take the smaller k value.

However, in this way, the complexity of the algorithm is the square level of n.

So we need to find the rule and then simplify the rule.

First, let’s analyze this problem: let the number with index i be x, then according to the problem conditions, we can know that when x < = i, the element counts as one point.

Therefore, the array index range of one point of element x is [x, n-1].

If we rotate the number of times k, then after the rotation, because it is a leftward rotation, the subscript after the rotation is (i - k + n) mod n

So, the range of (i - k + n) mod n should be [x, n - 1]

Do the math and you get, k < = (i - x + n) mod n, k > = (i + 1) mod n.

After removing the modulo operation, when i < x, i + 1 < = k < = i - x + n, when i > = x, k > = i + 1 or k < = i - x

For each element in the array nums, the rotation index range of 1 point for the element can be calculated according to the element value and the subscript of the element. After traversing all elements, you can get the number of elements corresponding to each rotation index. The rotation index with the most elements with 1 point is the rotation index with the highest score. If there are multiple rotation subscripts with the highest scores, take the smallest one among them.

Create an array of points of length n, where points [k] represents the score when the rotation index is k. For each element in the array nums, get the rotation index range of 1 point for that element, and then add 1 to all elements in that index range of array points. When the value of the elements in the array points is determined, find the smallest index of the largest element. The time complexity of this approach is still O (n ^ 2), and in order to reduce the time complexity, you need to use a differential array.

Assume that the initial index of element x is i. Add 1 to all elements in the index range [i + 1, i - x + n] of points when i < x, and add 1 to all elements in the index range [0, i - x] and [i + 1, n - 1] of points when i ≥ x. Since it is adding 1 to the elements within one or two consecutive subscript ranges, it can be implemented using a differential array. Define a difference array diffs of length n, where diffs [k] = points [k] − points [k − 1] (in particular, points [− 1] = 0), by: let low = (i + 1) mod n, high = (i − x + n + 1) mod n, add 1 to the value of diffs [low], subtract 1 from the value of diffs [high], and add 1 to the value of diffs [0] if low ≥ high.

After traversing all elements of the array nums and updating the difference array, traverse the array diffs and calculate the prefix sum, then the prefix sum at each subscript represents the score at the current rotation subscript. Maintain the minimum rotation subscript of the maximum score and the maximum score during the traversal process, and you can get the result after the traversal.

Here is the code for the C language version:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int bestRotation(int* nums, int numsSize){
    int* diffs = (int*)malloc(sizeof(int) * numsSize);
    memset(diffs, 0, sizeof(int) * numsSize);
    for(int i = 0; i < numsSize; i++) {
        int low = (i + 1) % numsSize;
        int high = (i - nums[i] + numsSize + 1) % numsSize;
        diffs[low]++;
        diffs[high]--;
        if (low >= high) {
            diffs[0]++;
        }
    }
    int bestIndex = 0, maxScore = 0, score = 0;
    for(int i = 0; i < numsSize; i++) {
        score += diffs[i];
        if (maxScore < score) {
            bestIndex = i;
            maxScore = score;
        }
    }
    free(diffs);
    return bestIndex;
}