189. Rotate Array

MediumArrayMathTwo Pointers
Leetcode Link

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:

  1. Reverse the entire array. This step puts the last k elements at the front, but in reversed order.
  2. Reverse the first k elements. This step puts these elements into the correct order at the start of the array.
  3. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

In a binary min heap, the minimum element can be found in:

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:

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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.

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

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

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:

  1. 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.

  2. Next, we take the last k elements of the array with the slice nums[-k:]. Since k is 2, this gives us [2, 3].

  3. Now, we take the rest of the array without the last k elements using nums[:-k]. This gives us [6, 7, 8, 1].

  4. 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].

  5. 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
Not Sure What to Study? Take the 2-min Quiz：

Which two pointer technique does Quick Sort use?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe Two pointers is a common interview technique

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫