Arrays: Practice Problems IV

A right rotation changes positions without changing values

A right rotation by k moves the value at source index i to destination index (i + k) % n. For [4, 2, 7, 1, 3], n = 5, and k = 2, each value moves two positions to the right. Values that pass the final index wrap around to the beginning, so the result is [1, 3, 4, 2, 7]. The five values are still present exactly once, but their positions have changed.

int[] values = {4, 2, 7, 1, 3};
int n = 5;
int k = 2;

// The destination of values[i] is (i + k) % n.
// values[0] = 4 moves to index 2.
// values[1] = 2 moves to index 3.
// values[2] = 7 moves to index 4.
// values[3] = 1 moves to index 0.
// values[4] = 3 moves to index 1.

Writing into the same array can destroy a value before you read it

The destination formula is correct, but using it directly on the original array is unsafe. Suppose you process source indices from left to right and write each value into its destination. At i = 0, the assignment puts 4 into index 2, changing the array to [4, 2, 4, 1, 3]. The original 7 has been overwritten before the loop reaches its source index, 2.

int[] values = {4, 2, 7, 1, 3};

for (int i = 0; i < 5; i++) {
    values[(i + 2) % 5] = values[i];
}

The first failure happens during the assignment for i = 0. The write goes to index (0 + 2) % 5, which is index 2, and destroys 7. When i = 2 arrives, values[2] no longer contains the original 7, so the loop copies 4 instead. Continuing the same order produces [2, 4, 4, 2, 4], not the required rotation. A later read cannot recover a value that an earlier write erased.

A second array preserves every source value until copying is complete

A temporary array separates reading from writing. Read every value from the unchanged original array, place it at its rotated destination in the temporary array, and only then copy the temporary result back. For the running example, the placements are 4 to index 2, 2 to index 3, 7 to index 4, 1 to index 0, and 3 to index 1. The temporary array becomes [1, 3, 4, 2, 7].

int[] values = {4, 2, 7, 1, 3};
int[] rotated = new int[5];
int n = 5;
int k = 2;

for (int i = 0; i < n; i++) {
    rotated[(i + k) % n] = values[i];
}

for (int i = 0; i < n; i++) {
    values[i] = rotated[i];
}

The first loop never writes into values, so every later read still sees its original value. The second loop copies the completed result back into values, producing [1, 3, 4, 2, 7]. This approach uses n extra array slots, five slots for this example, and its time cost is linear because each array is traversed once.

rotated[___] = values[i];

Three reversals rotate the array without a second array

You can avoid the second array by changing the order in three stages. First reverse all five values. Then reverse the first k values, which are the first two values here. Finally reverse the remaining n - k values, the final three values here. Each reversal swaps two positions, and one temporary variable preserves the value from one position while the swap is made.

int[] values = {4, 2, 7, 1, 3};
int n = 5;
int k = 2;

for (int left = 0, right = n - 1; left < right; left++, right--) {
    int temporary = values[left];
    values[left] = values[right];
    values[right] = temporary;
}
// [3, 1, 7, 2, 4]

for (int left = 0, right = k - 1; left < right; left++, right--) {
    int temporary = values[left];
    values[left] = values[right];
    values[right] = temporary;
}
// [1, 3, 7, 2, 4]

for (int left = k, right = n - 1; left < right; left++, right--) {
    int temporary = values[left];
    values[left] = values[right];
    values[right] = temporary;
}
// [1, 3, 4, 2, 7]

The first reversal moves the values that belong at the front toward the back and the values that belong at the back toward the front. Reversing the first two values puts 1, 3 in their final order. Reversing the final three puts 4, 2, 7 in their final order, giving [1, 3, 4, 2, 7]. Unlike the unsafe forward assignment, every swap saves one value before its slot is overwritten.