How to Rotate an Array in LeetCode Challenge 189

If you have an integer array nums, you can rotate the array to the right by k steps, where k is a non-negative number.

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 <= 10<sup>5</sup>

• -2<sup>31</sup> <= nums[i] <= 2<sup>31</sup> - 1

• 0 <= k <= 10<sup>5</sup>

Follow up:

• Try to think of as many solutions as possible. There are at least three different ways to solve this problem.

• Can you do it in-place with O(1) extra space?

Approach 1 - Using Iterate over array using modulus operator

class Solution {
    public void rotate(int[] nums, int k) {
        int count = nums.length;
       for(int i=0;i<k%count;i++){
        int temp = nums[count-1];   
        for(int j=count-1;j>0;j--){
            nums[j] = nums[j-1];
        }
        nums[0] = temp;        
       }        
    }    
}

Explanation:

1. Method Signature:

   • public void rotate(int[] nums, int k): This method takes an integer array nums and an integer k as parameters. k represents how many steps to rotate the array to the right.

2. Variable Initialization:

   • int count = nums.length;: This line sets count to the length of the nums array, which is the total number of elements in the array.

3. Outer Loop (for loop):

   • for (int i = 0; i < k % count; i++) {: This loop runs k % count times. If k is bigger than count (the length of the array), k % count makes sure that k wraps around the array length, so we don't do extra full rotations.

4. Inner Loop (for loop):

   • int temp = nums[count - 1];: This line saves the last element of the array in temp because it will be replaced during the rotation.

   • for (int j = count - 1; j > 0; j--) {: This loop goes from the second last element to the first element of the array.

     • nums[j] = nums[j - 1];: It shifts each element one position to the right, rotating the array to the right.

   • After the loop finishes, nums[0] = temp; puts the initially saved last element (temp) into the first position of the array, completing one step of the rotation.

5. Execution:

   • The outer loop makes sure the rotation happens k times (or fewer if k is more than count).

   • Each time the outer loop runs, it shifts the array to the right by one step.

Example:

If nums = [1, 2, 3, 4, 5] and k = 2:

• Initial state: [1, 2, 3, 4, 5]

• After the rotate method: [4, 5, 1, 2, 3]

This method rotates the array nums to the right by k steps using nested loops and a temporary storage (temp). It's worth mentioning that this approach has a time complexity of O(k * n), where n is the length of the array nums. Because of the nested loops, it might not be the most efficient for large k values.

Time and Space Complexity:

• Time Complexity: O(n⋅k)

  • n is the number of elements in the nums array.

  • k is the number of steps to rotate the array.

• Space Complexity: O(1)

  • The algorithm uses only a constant amount of extra space for temporary storage (temp).

Approach 2 - Using reversing Array

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--;
        }
    }
}

Explanation:

1. Method Signature:

   • public void rotate(int[] nums, int k): This method takes an integer array nums and an integer k as parameters. k represents the number of steps to rotate the array to the right.

2. Adjustk:

   • k %= nums.length;: This line makes sure that k stays within the range [0, nums.length-1]. Rotating an array by its length or any multiple of its length gives you the same array. So, by using k % nums.length, we get the right number of steps to rotate.

3. Usingreverse method:

   • reverse(nums, 0, nums.length - 1);: This step flips the entire array nums. After doing this, the array will be completely reversed.

   • reverse(nums, 0, k - 1);: Next, this step flips the first k elements of the array. After this, the first k elements will be in the right order for the rotated array.

   • reverse(nums, k, nums.length - 1);: Finally, this step flips the rest of the array, from index k to the end. After this, the elements from index k to the end will be in the right order for the rotated array.

Example:

If nums = [1, 2, 3, 4, 5, 6, 7] and k = 3:

• k %= 7 results in k = 3.

• reverse(nums, 0, 6) reverses the entire array: [7, 6, 5, 4, 3, 2, 1].

• reverse(nums, 0, 2) reverses the first k elements: [5, 6, 7, 4, 3, 2, 1].

• reverse(nums, 3, 6) reverses the remaining elements: [5, 6, 7, 1, 2, 3, 4].

After these operations, nums will be [5, 6, 7, 1, 2, 3, 4], which is the result of rotating the array [1, 2, 3, 4, 5, 6, 7] to the right by 3 steps

Time and Space Complexity:

• Time Complexity: O(n)

  • Three passes through the array, each reversing a segment of the array.

• Space Complexity: O(1)

  • Constant space used, aside from the input nums.

This article explores two different approaches to rotate an integer array to the right by k steps. The first approach uses a nested loop to shift elements one by one, achieving O(n * k) time complexity with O(1) space complexity. The second approach leverages array reversal, resulting in O(n) time complexity and O(1) space complexity. Examples and detailed explanations for both methods are provided.