mediumArray Basics (1D)

Right Rotate an Array by K Places

Rotate an array right by k positions. Values shifted off the end wrap around to the start.

LeetCode ↗

Work through the cases

3 examples

Input notation

Array values on line 1; a nonnegative integer k on line 2. The array is nonempty.

Expected result

The rotated array, space-separated.

Case 1

Input

1 2 3 4 5
2

Expected output

4 5 1 2 3

Case 2

Input

8 9
3

Expected output

9 8

Case 3

Input

1 2 3
0

Expected output

1 2 3

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

Rotate right by k. A second array is O(n) space; n ≤ 10^5, and the follow-up wants in-place. A right rotate by k moves the last k items to the front. Reverse the whole array, then reverse the first k and the last n-k. Three reversals, only swaps.

We can assume the length of the array is n and calculate the actual number of steps needed by taking the module of k and n, which is k \bmod n.

Next, let us reverse three times to get the final result:

1. Reverse the entire array. 2. Reverse the first k elements. 3. Reverse the last n - k elements.

For example, for the array [1, 2, 3, 4, 5, 6, 7], k = 3, n = 7, k \bmod n = 3.

1. In the first reverse, reverse the entire array. We get [7, 6, 5, 4, 3, 2, 1]. 2. In the second reverse, reverse the first k elements. We get [5, 6, 7, 4, 3, 2, 1]. 3. In the third reverse, reverse the last n - k elements. We get [5, 6, 7, 1, 2, 3, 4], which is the final result.

The time complexity is O(n), where n is the length of the array. The space complexity is O(1).

class Solution {
    private int[] nums;

    public void rotate(int[] nums, int k) {
        this.nums = nums;
        int n = nums.length;
        k %= n;
        reverse(0, n - 1);
        reverse(0, k - 1);
        reverse(k, n - 1);
    }

    private void reverse(int i, int j) {
        for (; i < j; ++i, --j) {
            int t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.