Leetcode 189. Rotate Array
Problem Explanation
We are given an array of values and a number k
. We are required to rotate the elements of the array to the right by k
steps.
Let's take an example for better understanding. Suppose the input array is [2,4,6,8] and k=2. So after the first rotation, the array would be [8,2,4,6] and after 2 rotations, it would transform to [6,8,2,4]. That is your solution.
The challenge in this problem can be focussing on two aspects i.e.
- Device as many solutions as you can.
- Could you do it in-place with O(1) extra space?
Solution Approach
A simple and efficient solution for this problem would be to use reversing of array in three steps.
Let's take an example for understanding the approach in-step, assume array=[1,2,3,4,5,6,7] and k=3
- The first step involves reversing the entire array i.e [7,6,5,4,3,2,1].
- The second step involves reversing the first 'k' elements i.e [5,6,7,4,3,2,1]
- The third step is reversing the rest of the array i.e [5,6,7,1,2,3,4].
This approach is efficient as it requires O(1) space and O(n) time.
Python Solution
1 2python 3class Solution: 4 def rotate(self, nums: List[int], k: int) -> None: 5 """ 6 Do not return anything, modify nums in-place instead. 7 """ 8 k = k % len(nums) # handle scenarios where k>len(nums) 9 10 def reverse(left: int, right: int) -> None: 11 while left < right: 12 nums[left], nums[right] = nums[right], nums[left] 13 left, right = left + 1, right - 1 14 15 reverse(0, len(nums) - 1) # First step 16 reverse(0, k - 1) # Second step 17 reverse(k, len(nums) - 1) # Third step
Java Solution
1
2java
3class Solution {
4 public void rotate(int[] nums, int k) {
5 k %= nums.length;
6 reverse(nums, 0, nums.length - 1);
7 reverse(nums, 0, k - 1);
8 reverse(nums, k, nums.length - 1);
9 }
10
11 public void reverse(int[] nums, int start, int end) {
12 while (start < end) {
13 int temp = nums[start];
14 nums[start] = nums[end];
15 nums[end] = temp;
16 start++;
17 end--;
18 }
19 }
20}
C++ Solution
1
2cpp
3class Solution {
4public:
5 void rotate(vector<int>& nums, int k) {
6 k = k % nums.size();
7 reverse(nums.begin(), nums.end());
8 reverse(nums.begin(), nums.begin() + k);
9 reverse(nums.begin() + k, nums.end());
10 }
11};
Javascript Solution
1 2javascript 3const reverse = (nums, start, end) => { 4 while(start < end) { 5 [nums[start], nums[end]] = [nums[end], nums[start]]; 6 start++; 7 end--; 8 } 9}; 10 11var rotate = function(nums, k) { 12 k = k%nums.length; 13 reverse(nums, 0, nums.length - 1); 14 reverse(nums, 0, k - 1); 15 reverse(nums, k, nums.length - 1); 16};
C# Solution
1
2csharp
3public class Solution {
4 public void Rotate(int[] nums, int k) {
5 k %= nums.Length;
6 Reverse(nums, 0, nums.Length - 1);
7 Reverse(nums, 0, k - 1);
8 Reverse(nums, k, nums.Length - 1);
9 }
10
11 private void Reverse(int[] nums, int start, int end) {
12 while (start < end) {
13 int temp = nums[start];
14 nums[start++] = nums[end];
15 nums[end--] = temp;
16 }
17 }
18}
The different solutions are essentially implementing the same algorithm just with the respective language's syntax. The reverse function that we're using is a simple function that swaps the values from beginning and the end, then increment/decrement the pointers respectively till the start pointer is less than the end.# Swift Solution
1 2swift 3class Solution { 4 func rotate(_ nums: inout [Int], _ k: Int) { 5 var k = k % nums.count 6 reverse(0, nums.count - 1, &nums) 7 reverse(0, k - 1, &nums) 8 reverse(k, nums.count - 1, &nums) 9 } 10 11 private func reverse(_ start: Int, _ end: Int, _ nums: inout [Int]) { 12 var start = start 13 var end = end 14 while start < end { 15 let temp = nums[start] 16 nums[start] = nums[end] 17 nums[end] = temp 18 start += 1 19 end -= 1 20 } 21 } 22}
Ruby Solution
1 2ruby 3# @param {Integer[]} nums 4# @param {Integer} k 5# @return {Void} Do not return anything, modify nums in-place instead. 6def rotate(nums, k) 7 k = k % nums.length 8 reverse(nums, 0, nums.length - 1) 9 reverse(nums, 0, k - 1) 10 reverse(nums, k, nums.length - 1) 11end 12 13def reverse(nums, left, right) 14 while(left < right) 15 nums[left], nums[right] = nums[right], nums[left] 16 left += 1 17 right -= 1 18 end 19end
In these solutions, we are performing the same algorithm as in Python, Java, C++, C#, and Javascript before: the array is reversed entirely first, then the first k elements are reversed individually, and lastly the elements from k to the end of the array are reversed.
The difference lays in the language syntax, but the logic remains the same across all languages. These solutions have the same time complexity O(n) and space complexity O(1) in each programming language making it a very efficient solution.
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.