Rotate Array

MEDIUM

Description

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

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 <= 10⁵
-2³¹ <= nums[i] <= 2³¹ - 1
0 <= k <= 10⁵

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?

Approaches

Checkout 4 different approaches to solve Rotate Array. Click on different approaches to view the approach and algorithm in detail.

Brute Force: Rotate One by One

This approach simulates the rotation process step by step. For each of the k rotation steps, it moves every element in the array one position to the right. The last element is moved to the first position.

Algorithm

1. Calculate the effective rotation count by taking k = k % nums.length.
1. Repeat the rotation process k times.
1. In each of the k iterations, perform a single right rotation:
- a. Store the last element of the array in a temporary variable, last = nums[n-1].
- b. Shift all elements from index n-2 down to 0 one position to the right. This can be done by iterating from j = n-1 down to 1 and setting nums[j] = nums[j-1].
- c. Place the stored last element at the beginning of the array: nums[0] = last.

The most straightforward way to solve the problem is to literally rotate the array k times. A single right rotation involves taking the last element and moving it to the front, while shifting every other element one position to the right.

We can implement this by running a loop k times. Inside this loop, we perform the single rotation. To avoid unnecessary rotations when k is larger than the array length n, we first take k = k % n.

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        // To handle cases where k > n
        k %= n;
        
        for (int i = 0; i < k; i++) {
            int lastElement = nums[n - 1];
            // Shift all elements one position to the right
            for (int j = n - 1; j > 0; j--) {
                nums[j] = nums[j - 1];
            }
            // Place the last element at the front
            nums[0] = lastElement;
        }
    }
}

Complexity Analysis

Time Complexity: O(n * k)Space Complexity: O(1)

Pros and Cons

Pros:

Simple to understand and implement.
It's an in-place solution, using constant extra space.

Cons:

Extremely inefficient for large arrays or large values of k.
Will likely result in a 'Time Limit Exceeded' (TLE) error on most coding platforms for larger constraints.

Code Solutions

Checking out 5 solutions in different languages for Rotate Array. Click on different languages to view the code.

public class Solution {
    private int[] nums;
    public void Rotate(int[] nums, int k) {
        this.nums = nums;
        int n = nums.Length;
        k %= n;
        reverse(0, n - 1);
        reverse(0, k - 1);
        reverse(k, n - 1);
    }
    private void reverse(int i, int j) {
        for (; i < j; ++i, --j) {
            int t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
    }
}

Video Solution

Watch the video walkthrough for Rotate Array

Patterns:

MathTwo Pointers

Data Structures:

Array

Companies:

Accenture |American Express |Capgemini |EPAM Systems |