189. Rotate Array

Problem Description

In this problem, we are given an array of integers named nums. The goal is to rotate the elements of the array to the right by k steps. When we rotate the array, every element moves k places to the right, and the elements at the end of the array wrap around to the beginning. For example, if the array is [1, 2, 3, 4, 5] and k is 2, the rotated array will be [4, 5, 1, 2, 3]. It is important to note that k is non-negative, which means rotating by k steps always moves elements to the right, and may be larger than the length of the array.

Intuition

The key to approaching this problem is to understand that rotating an array by k steps to the right is equivalent to taking the last k elements and moving them to the front, while shifting the remaining elements to make space. However, if k is larger than the length of the array, rotating the array k times would effectively be the same as rotating it k % len(nums) times since every len(nums) rotations, the array returns to its original configuration.

To optimize the array rotation, we can follow a three-step reversal strategy which essentially achieves the rotation without additional storage for the displaced elements:

Reverse the entire array. This step puts the last k elements at the front, but in reversed order.
Reverse the first k elements. This step puts these elements into the correct order at the start of the array.
Reverse the last n - k elements, where n is the length of the array. This will fix the order of the rest of the array.

This method capitalizes on the idea that reversing specific parts of the array can be used to manipulate the positions of the elements with respect to each other, achieving the same result required by the rotation.

Learn more about Math and Two Pointers patterns.

Solution Approach

The given Python solution implements the concept of array rotation by leveraging array slicing and concatenation. This method can be thought of as a one-step approach to the three-step reversal strategy outlined in the Reference Solution Approach. Let's break down the solution approach step by step:

To handle cases where k is greater than the length of the array n, we use k %= len(nums). This calculates k modulo n, which effectively reduces k to the minimum number of steps needed to achieve the same resulting rotation.
The operation nums[-k:] obtains a slice of the last k elements of the array. These are the elements that need to be moved to the front of the array.
The operation nums[:-k] gets the slice of the array without the last k elements. This is the part of the array that will be shifted rightward by k positions.
By concatenating nums[-k:] + nums[:-k], we are effectively placing the last k elements in front of the rest of the array, thus completing the rotation.
Finally, the slice assignment nums[:] updates the entire original array in place with the rotated version. This allows us to modify the array without returning anything, as the function signature requires the transformation to be applied in place.

It's important to note that no additional data structures are used in this approach. The slicing and concatenation operations take advantage of the Python language's capabilities to handle list manipulation efficiently.

This solution highlights a pattern often used in array manipulation problems — the clever use of slicing to avoid a more complex and potentially less efficient series of array operations.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example to illustrate the solution approach given in the content above. Suppose we have an array nums with the elements [6, 7, 8, 1, 2, 3] and k equals 2.

We would like to rotate this array k steps to the right. Here's how we do it step by step:

First, we need to take care of cases where k may be greater than the length of nums. In our case, k is less than the length of nums, so k %= len(nums) does not change the value of k. If the nums array was shorter or k larger, this step would be critical to prevent unnecessary rotations.
Next, we take the last k elements of the array with the slice nums[-k:]. Since k is 2, this gives us [2, 3].
Now, we take the rest of the array without the last k elements using nums[:-k]. This gives us [6, 7, 8, 1].
We then concatenate the slices obtained in steps 2 and 3. So, nums[-k:] + nums[:-k] equals [2, 3] + [6, 7, 8, 1], which results in the array [2, 3, 6, 7, 8, 1].
The final step is to update the original array nums with the rotated version by using the slice assignment nums[:]. So, nums[:] becomes [2, 3, 6, 7, 8, 1].

The original array nums is now rotated k steps to the right, and our final result is [2, 3, 6, 7, 8, 1]. No extra space was used; we've simply manipulated nums to its rotated form in place by using array slicing and concatenation.

Solution Implementation

1from typing import List
2
3class Solution:
4    def rotate(self, nums: List[int], k: int) -> None:
5        """Rotates the elements of the array to the right by k steps."""
6        # The effective rotation needed when k is larger than the array's length
7        k %= len(nums)
8      
9        # Perform rotation
10        # The last k elements are moved to the front and the remainder are appended
11        nums[:] = nums[-k:] + nums[:-k]
12

1class Solution {
2    // Class-level variable to store the input array
3    private int[] nums;
4
5    /**
6     * Rotates the given array to the right by k steps.
7     * @param nums Array to be rotated.
8     * @param k Number of steps to rotate the array to the right.
9     */
10    public void rotate(int[] nums, int k) {
11        // Assign the input array to the class-level variable
12        this.nums = nums;
13
14        // Number of elements in the array
15        int n = nums.length;
16
17        // Normalize the number of steps k to avoid extra rotations
18        k %= n;
19
20        // Reverse the entire array
21        reverse(0, n - 1);
22
23        // Reverse the first part (up to k elements)
24        reverse(0, k - 1);
25
26        // Reverse the second part (from k to the end of the array)
27        reverse(k, n - 1);
28    }
29
30    /**
31     * Reverses elements in the array between indices i and j.
32     * @param i Starting index for reversal.
33     * @param j Ending index for reversal.
34     */
35    private void reverse(int i, int j) {
36        // Using two pointers approach, swap elements until pointers meet or cross
37        while (i < j) {
38            // Temporary variable to hold a value during the swap
39            int temp = nums[i];
40
41            // Perform swap
42            nums[i] = nums[j];
43            nums[j] = temp;
44
45            // Move pointers towards each other
46            ++i;
47            --j;
48        }
49    }
50}
51

1#include <vector>  // Include the vector header for vector usage
2
3class Solution {
4public:
5    // This function rotates the elements of 'nums' to the right by 'k' steps
6    void rotate(vector<int>& nums, int k) {
7        int num_elements = nums.size();  // Get the number of elements in the vector
8        k %= num_elements;               // Ensure k is within the bounds of the vector's size
9      
10        // Reverse the entire vector
11        reverse(nums.begin(), nums.end());  // This puts the last k elements in front
12
13        // Reverse the first k elements to restore their original order
14        reverse(nums.begin(), nums.begin() + k);
15
16        // Reverse the remaining elements to restore their original order
17        reverse(nums.begin() + k, nums.end());
18    }
19};
20

1/**
2 * Rotates the array `nums` to the right by `k` steps.
3 * This version of the function is written with clearer naming, added comments, and maintains
4 * the same in-place strategy for modifying the input array.
5 * @param nums The input array of numbers to be rotated.
6 * @param k The number of steps to rotate the array.
7 */
8function rotate(nums: number[], k: number): void {
9    const arrayLength: number = nums.length;
10    // Ensure the rotation steps are within the array bounds.
11    k %= arrayLength; 
12  
13    /** 
14     * Reverses the elements within the portion of the array from index `start` to `end`.
15     * @param start The starting index of the portion to reverse.
16     * @param end The ending index of the portion to reverse.
17     */
18    const reverse = (start: number, end: number): void => {
19        while (start < end) {
20            // Swap the elements at the `start` index and the `end` index.
21            const temp: number = nums[start];
22            nums[start] = nums[end];
23            nums[end] = temp;
24          
25            // Move towards the middle of the array from both ends.
26            start++;
27            end--;
28        }
29    };
30  
31    // Reverse the whole array.
32    reverse(0, arrayLength - 1);
33    // Reverse the first part (0 to k-1).
34    reverse(0, k - 1);
35    // Reverse the second part (k to n-1).
36    reverse(k, arrayLength - 1);
37}
38

Time and Space Complexity

The time complexity of the code is O(n) where n is the length of the array, because it involves slicing the array into two parts and then concatenating them, both of which take O(n) operations.

The space complexity is O(1) because the rotation operation modifies the array in-place. Although slicing the array appears to create new arrays, this is handled under the hood by Python and does not require additional space proportional to the size of the input array.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right

<, left, right

<=, right, left

<, right, left

I don’t know