020.md

189. Rotate Array

Difficulty: 🟡 Medium

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

Examples:

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation: 
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

Constraints:

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

Follow up:

• Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
• Could you do it in-place with O(1) extra space?

Solutions

O(n) solution without extra space in Python3 and Java

Example

k = 3 nums = [1, 2, 3, 4, 5, 6, 7]
--------------------------------------------------------------------------------
source: 0 target: 3
[4, 2, 3, 1, 5, 6, 7]
--------------------------------------------------------------------------------
source: 0 target: 6
[7, 2, 3, 1, 5, 6, 4]
--------------------------------------------------------------------------------
source: 0 target: 2
[3, 2, 7, 1, 5, 6, 4]
--------------------------------------------------------------------------------
source: 0 target: 5
[6, 2, 7, 1, 5, 3, 4]
--------------------------------------------------------------------------------
source: 0 target: 1
[2, 6, 7, 1, 5, 3, 4]
--------------------------------------------------------------------------------
source: 0 target: 4
[5, 6, 7, 1, 2, 3, 4]
--------------------------------------------------------------------------------
source: 0 source: 0
[5, 6, 7, 1, 2, 3, 4]
--------------------------------------------------------------------------------

Python3

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        length = len(nums)
        source, target = 0, 0
        for _ in range(length):
            target = (target + k) % length
            if source == target:
                source += 1
                target += 1 
            else: 
                nums[target], nums[source] = nums[source], nums[target]

Java

class Solution {
    public void rotate(int[] nums, int k) {
        int length = nums.length;
        int source = 0;
        int target = 0;

        for(int i = 0; i < length; i++) {
            target = (target + k) % length;
            if (source == target) {
                source++;
                target++;
            } else {
                int temp = nums[target];
                nums[target] = nums[source];
                nums[source] = temp;
            }
        }
    }
}

The given solution solves the problem by performing the following steps:

1. Initialize a variable length to store the length of the array nums.
2. Initialize two variables source and target to keep track of the indices while swapping elements.
3. Iterate length number of times:
   • Calculate the new target index by adding k to the current target index and taking the modulo length.
   • Check if source is equal to target. If they are equal, increment both source and target by 1 to move to the next element.
   • Otherwise, swap the elements at indices source and target in the array nums.
4. After the iteration, the array nums will be rotated to the right by k steps.

Complexity Analysis

The time complexity of this algorithm is O(n), where n is the length of the array nums. This is because the algorithm performs a single pass through the array to swap the elements.

The space complexity of the algorithm is O(1) since it does not use any additional data structures that grow with the input size. The modifications are done in-place, so the memory usage remains constant regardless of the input size.

Summary

The given solution effectively rotates the array nums to the right by k steps in-place. It achieves this by swapping the elements using two pointers, source and target, and performing a single pass through the array. The algorithm has a time complexity of O(n) and a space complexity of O(1), making it an efficient solution for the problem.

NB: If you want to get community points please suggest solutions in other languages as merge requests.