Right Rotate an Array by K places | Explained with Examples

In this article we’ll guide you through the Python program to Right Rotate an Array by K places (in-place) [Problem Link]. We will see brute force, better and optimal solution to Right Rotate an Array by K places and dry run with images to understand the solution properly. So let’s begin.

Understand the problem

The problem is asking us to rotate an array to the right by k positions. This means that each element in the array will shift to the right, and the last k elements will move behind the beginning element.

What Does Rotation Mean?

• If k = 1, the last element moves to the first position.
• If k = 2, the last two elements move to the front, shifting everything else.
• If k is greater than the array length, we rotate it as if k % n times (where n is the length of the array).

Examples to Understand Rotation

Example 1

Input:

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

Step-by-Step Rotation:

1. Move last 3 elements [5,6,7] to the front.
2. Shift the remaining [1,2,3,4] to the right.

Output:

nums = [5, 6, 7, 1, 2, 3, 4]

Example 2

Input:

nums = [-1, -100, 3, 99]
k = 2

Step-by-Step Rotation:

1. Move last 2 elements [3, 99] to the front.
2. Shift the remaining [-1, -100] to the right.

Output:

nums = [3, 99, -1, -100]

Example 3 (Large k value)

Input:

nums = [10, 20, 30, 40, 50, 60, 70, 80]
k = 10

Since k > n (array length is 8), we take k % n = 10 % 8 = 2.
So, we rotate by 2 places instead of 10.

Output:

nums = [70, 80, 10, 20, 30, 40, 50, 60]

Constraints:

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

Also read about the Python Program to Move Zeros to End of the Array.

1. Brute Force Solution (Using Pop and Insert)

This solution will contain pop method which removes the last element from the array and then use insert method to put the element at first. Doing so, we rotated our array by 1 time. Let’s see multiple rotations can lead to our answer.

Intuition and Approach

Given that rotating an array of length n by n times (or a multiple of n) results in the array looking the same as the original, the actual number of effective rotations needed is k % len(nums). This approach ensures the minimal number of steps required to achieve our result, optimizing performance when k is larger than len(nums).

The logic we will apply is pretty simple:

• Determine the number of necessary rotations using k % len(nums).
• For each rotation, remove the last element of the array (nums.pop()) and insert it at the beginning (nums.insert(0, last)). This simulates a single right rotation.

Code

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # Becuase if k = 8 and length = 7, means
        # we should only rotate 1 time instead of 8 times
        rotations = k % len(nums)

        for _ in range(rotations):
            last = nums.pop()
            nums.insert(0, last)

Code Explanation (Stey by Step)

1. Calculating Actual Rotations Needed:
   1. The rotations variable is assigned the value of k % len(nums) to ensure only the necessary number of rotations are performed.
2. Rotation Loop:
   • The loop runs rotations times. Each iteration performs one right rotation.
   • last = nums.pop(): Removes the last element of the array and stores it in last.
   • nums.insert(0, last): Inserts the last element at the start of the array, thus rotating the array right by one position.

Dry Run (with images)

Let’s go through the code step by step, using images to illustrate the detailed dry run process.

Edge cases to consider

• k Equal to Zero: If k is 0, the array should remain unchanged. Our code handles this naturally since rotations would be 0, and no loop iterations would occur.
• k Greater than Array Length: As shown in the example, our code recalculates k to ensure only necessary rotations are done.
• Empty Array: If nums is empty, our code should handle it properly, performing no actions.
• Array of Length One: An array with one element remains unchanged regardless of k, which our code will handle correctly since popping and inserting the same element does not alter the array.

Time and Space Complexity

• Time Complexity: The complexity is O(k×n), where k is the number of rotations (after modulo operation) and n is the number of elements in the array. Each rotation involves a pop operation (O(1)) and an insert operation at the beginning of the array (O(n)), making it inefficient for large arrays or high values of k.
• Space Complexity: The space complexity is O(1) since no additional space is used and it does not depend on the size of the array.

2. Better Solution (Using Slicing)

This solution will contain slice method which is available in python to achieve our rotation and get our answer. You need to have a basic understanding of how slicing works in Python to understand the solution.

Intuition and Approach

The approach used here takes advantage of slicing in Python to rearrange segments of the array rather than manually moving elements. The core idea involves:

1. Modifying k to be within the range of the array’s length using the modulus operation (k %= n). This handles cases where k is greater than the length of the array, reducing unnecessary full rotations.
2. Slicing the array into two segments:
   • The last k elements: nums[n-k:]
   • The first n-k elements: nums[:n-k]
3. Concatenating these two list/array in reverse order to achieve the desired right rotation.

Code

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k %= n

        # Rotate the list in-place
        nums[:] = nums[n - k :] + nums[: n - k]

Code Explanation (Step by Step)

1. Initialization:
   • n is set to the length of the array nums.
   • k is recalculated as k % n to ensure there isn’t any unnecessary rotations.
2. Rotation via Slicing:
   1. The array nums is updated by slicing and concatenating:
      • nums[n-k:] captures the last k elements which will move to the front of the array.
      • nums[:n-k] captures the remaining elements which will shift rightwards.
   2. These slices are concatenated to form the new order of elements in nums.

Dry Run

Let’s use the input nums = [1, 2, 3, 4, 5] and k = 3 as an example:

1. Initial State: nums = [1, 2, 3, 4, 5], n = 5, k = 3
2. Calculate Effective Rotations:
   • k = 3 % 5 = 3
3. Rotate Operation:
   • The last k elements are nums[5-3:5] = nums[2:5] = [3, 4, 5].
   • The first n-k elements are nums[0:5-3] = nums[0:2] = [1, 2].
   • Concatenation results in nums[:] = [3, 4, 5] + [1, 2] = [3, 4, 5, 1, 2].
4. Final State: nums = [3, 4, 5, 1, 2]

Edge cases to consider

• k Equal to Zero: If k is 0, the array remains unchanged. The method adjusts for this since nums[n-k:] and nums[:n-k] simply makes the original array.
• k Greater than Array Length: The method correctly recalculates k to fit within the array bounds, preventing unnecessary rotations.
• Empty Array: If nums is empty, our code handles this by not performing any actions since slicing an empty array remains empty.
• Array of Length One: An array with one element remains unchanged regardless of k, which our code handles correctly as slicing and concatenating a single element array does not change it.

Time and Space Complexity

• Time Complexity: The complexity is O(n) due to the slicing operations, where each slice operation handles all elements.
• Space Complexity: The complexity is O(n) as the slicing operation creates new slices which are then used to overwrite the original array in-place.

Efficiency: This method is more efficient than manually rotating each element or using additional arrays. It takes advantage of Python’s powerful slicing capabilities to perform the rotation cleanly and efficiently. However, space usage could be a concern due to the temporary slices, although the operation itself is performed in-place.

3. Optimal Solution (Using While Loop and Reversing Array)

Before jumping on to this solution, please refer How to Reverse an Array using Loops.

Intuition and Approach

The approach we will apply uses reversals of array or a part of array to achieve the rotation without extra space for another array. The process is as follows:

1. Normalize k to be less than the length of the array using k %= n. This handles cases where k is larger than the array size, reducing rotations.
2. Reverse the last k elements of the array. This positions these elements as they should appear after a complete rotation.
3. Reverse the first n-k elements. This prepares the front part of the array for a reversal.
4. Reverse the entire array to finalize the positions of the elements for the right rotation.

Code

class Solution:
    def reverse(self, nums: List[int], l: int, r: int) -> None:
        """
        Reverse the portion of nums starting at index l up to index r in-place.
        """
        while l < r:
            nums[l], nums[r] = nums[r], nums[l]
            l += 1
            r -= 1

    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k %= n  # Handle cases where k might be larger than n

        # 1. Reverse the last k elements
        self.reverse(nums, n - k, n - 1)

        # 2. Reverse the first n-k elements
        self.reverse(nums, 0, n - k - 1)

        # 3. Reverse the entire array
        self.reverse(nums, 0, n - 1)

Code Explanation (Step by Step)

1. Helper Function – Reverse:
   1. A helper function reverse(l, r) is defined to reverse the elements of nums between indices l and r, inclusive. This function swaps elements from the outermost until it reaches the middle of the specified segment.
2. Initialization and Normalization:
   1. n is set to the length of nums.
   2. k is recalculated as k % n to ensure rotations are within bounds.
3. Rotation Steps:
   1. reverse(n – k, n – 1): Reverse the segment of the array that contains the last k elements.
   2. reverse(0, n – k – 1): Reverse the segment of the array before the last k elements.
   3. reverse(0, n – 1): Finally, reverse the entire array to align all elements correctly after the rotation.

Dry Run (with images)

Let’s go through the code step by step, using images to illustrate the detailed dry run process.

Edge cases to consider

• k Equal to Zero: If k is 0, the array remains unchanged. Our code handles this as the reversals will effectively leave the array as is.
• k Greater than Array Length: Our code correctly recalculates k to fit within the array bounds, ensuring efficient rotations.
• Empty Array: If nums is empty, our code avoids any operations, preserving the empty state.
• Array of Length One: An array with one element remains unchanged regardless of k, which our code correctly handles since the operations do not change a single-element array.

Time and Space Complexity

• Time Complexity: The complexity is O(n) because each element is touched a constant number of times across the three reversal operations.
• Space Complexity: The complexity is O(1) as the solution modifies the array in place and does not use additional space proportional to the input size.

Efficiency: This method is efficient in terms of both time and space. By using reversals, it avoids the need for extra storage and minimizes the number of operations, making it suitable for large datasets. The reversals ensure that each element is moved directly to its final position, optimizing the process compared to other methods that might involve multiple shifts or rotations.

For any changes to the document, kindly email at code@codeanddebug.in or contact us at +91-9712928220.