Crash Code Part-4 (Rotate That Array!)

Problem Description

You are given a list of integers. Your task is to rotate the list to the right by k steps, where k is a non-negative integer. Each rotation moves the last element to the front of the list. The catch? We want to do this efficiently without relying on extra arrays, built-in rotation methods, or external helper functions. Everything needs to happen right inside the main method.

Constraints

• 1 <= n <= 10^5
• -2^31 <= nums[i] <= 2^31 - 1
• 0 <= k <= 10^5

Input

• The first line contains an integer n, the number of elements in the list.
• The next n lines each contain one integer, representing elements of the list.
• The last line contains a non-negative integer k, representing the number of right rotations.

Output

Return the rotated list of size n as output (the driver code handles printing).

Examples

Example

Input:

7
1
2
3
4
5
6
7
3

Output:

5
6
7
1
2
3
4

Explanation:

n = 7, so the list is [1, 2, 3, 4, 5, 6, 7]
k = 3, so we need to rotate the array 3 times to the right.

1. Rotate right by 1: [7, 1, 2, 3, 4, 5, 6]
2. Rotate right by 2: [6, 7, 1, 2, 3, 4, 5]
3. Rotate right by 3: [5, 6, 7, 1, 2, 3, 4]

The Concepts Under the Hood

Instead of manually shifting elements one by one (which is too slow, running in O(n^k) time) or creating a whole new list (which uses extra memory, running in O(n) space), we can use the Array Reversal Algorithm.

It relies on a neat logical trick using three simple steps to achieve an O(n) time and O(1) auxiliary space solution:

1. The Modulo Math: Rotating an array of size n by n steps leaves it completely unchanged. So, we optimize our rotations by taking the modulo: k = k % n. This prevents unnecessary looping if k is larger than the array size.
2. Reverse the entire array: This puts the elements that need to be at the front generally at the front, but their internal order is backwards.
3. Reverse the first k elements: This fixes the order of the newly moved front elements.
4. Reverse the remaining n - k elements: This fixes the order of the original front elements that were shifted to the right side of the list.

Visualizing the Two-Pointer Swap

Since we are constrained to avoid external helper methods, we execute a standard two-pointer reversal directly inline. Here is how the two-pointer technique looks in action when we reverse the entire array (Step 2 of our algorithm) for the list [1, 2, 3, 4, 5, 6, 7].

We set a left pointer at the start (index 0) and a right pointer at the end (index 6). We swap their values, then move them towards each other until they cross.

Initial State:

[ 1, 2, 3, 4, 5, 6, 7 ]
  ^L                 ^R

Swap 1: (Swap 1 and 7, move pointers inwards)

[ 7, 2, 3, 4, 5, 6, 1 ]
     ^L           ^R

Swap 2: (Swap 2 and 6, move pointers inwards)

[ 7, 6, 3, 4, 5, 2, 1 ]
        ^L     ^R

Swap 3: (Swap 3 and 5, move pointers inwards)

[ 7, 6, 5, 4, 3, 2, 1 ]
           ^L ^R

Once left is no longer strictly less than right (in this case, they meet at index 3, value 4), the loop terminates. The array segment is fully reversed in-place without needing a second array! We just repeat this exact logic for the sub-segments in steps 3 and 4 to finish the rotation.

Solve

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

import java.io.*;
import java.util.*;

class Result {
    public static List rotateArray(List nums, int k) {
        int n = nums.size();
        // Handle cases where the list is empty or k is exactly a multiple of n
        if (n == 0 || k % n == 0) {
            return nums;
        }

        // Effective rotations needed if k > n
        k = k % n;

        // 1. Reverse the entire list
        int left = 0;
        int right = n - 1;
        while (left < right) {
            int temp = nums.get(left);
            nums.set(left, nums.get(right));
            nums.set(right, temp);
            left++;
            right--;
        }

        // 2. Reverse the first k elements
        left = 0;
        right = k - 1;
        while (left < right) {
            int temp = nums.get(left);
            nums.set(left, nums.get(right));
            nums.set(right, temp);
            left++;
            right--;
        }

        // 3. Reverse the remaining n - k elements
        left = k;
        right = n - 1;
        while (left < right) {
            int temp = nums.get(left);
            nums.set(left, nums.get(right));
            nums.set(right, temp);
            left++;
            right--;
        }

        return nums;
    }
}