Intuition

The problem requires us to move elements in the array to the right while maintaining their relative order. When an array is rotated, the last k elements will come to the front of the array, and the first n-k elements will shift to the back. A practical way to achieve this without using extra space is to reverse segments of the array.

Approach

1. Normalize k: Since rotating the array by its length results in the same array, we first reduce k to k % n (where n is the length of the array) to handle cases where k is greater than n.

2. Reverse the entire array: This will place the last k elements in the first k positions but in reverse order.

3. Reverse the first k elements: This step will correct the order of the last k elements to be in the original order.

4. Reverse the remaining n - k elements: This step will correct the order of the first n - k elements to maintain their relative order.

Complexity

• Time complexity:

O(n), where n is the number of elements in the array. Each element is reversed a constant number of times, leading to linear time complexity.

• Space complexity:

O(1), as the operation is performed in place without using any additional arrays or data structures.

Code

Java

class Solution {
    public void rotate(int[] nums, int k) {
       int n=nums.length;
        k = k % n; // Normalize k

        //reverse entire  array
       reverse(nums,0,n-1);

       //reverser first k elemets 
       reverse(nums,0,k-1);

       //reverse remaining from kth elements
       reverse(nums,k,n-1);
       
    }

    private void reverse(int arr[],int start, int end){
        while(start<end){
            int temp=arr[start];
            arr[start]=arr[end];
            arr[end]=temp;
            start++;
            end--;
        }
    }
}