Rotate Array

Question

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation: 
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

Constraints:

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1
• 0 <= k <= 105

Approach

We will use the combination of array reversal and modular arithmetic. The steps are as follows

1. Normalize k:

• First , let us ensure that k is within the range of the array length. We can do this by taking the modular operation k % length of the array. This will make sure that k represent the effective number of steps to rotate.

2. Reverse the Entire Array:

• We will reverse the whole array.
• Reversing will flip the whole array elements completely.

3. Reverse the first k elements:

• The whole array is reversed . We will reverse the first element k separately.
• The last k elements will move to the beginning of the array.

4. Reverse the Remaining elements:

• Finally, we reverse the elements from position k to the end of the array. This action ensures that the elements shifted to the beginning in the previous step are now placed at the end in their correct order.

Dry Run

Consider the array nums = [ 1, 2, 3, 4, 5, 6, 7 ] and k = 3 .

1. Initial array:

2. Normalize k:

• k=3 and the length of the array is 7, k remains the same.

3. Reverse the Entire Array:

• Reverse all elements in the array.

4. Now we are reversing first 3 elements of k only.

• Now we are reversing first 3 elements of k only.

5. Reverse the Remaining elements

• We will reverse the remaining array

Code:

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

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

Complexity

• Time complexity : O(n).
• Space complexity : O(1).