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.

1. Device as many solutions as you can.
2. 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

1. The first step involves reversing the entire array i.e [7,6,5,4,3,2,1].
2. The second step involves reversing the first 'k' elements i.e [5,6,7,4,3,2,1]
3. 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.