Rotate Array

Problem Statement

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 step 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 step to the right: [99,-1,-100,3]
  • Rotate 2 steps to the right: [3,99,-1,-100]

Approaches

1. Brute Force Approach

The brute force approach involves rotating the array one step at a time, k times.

Time Complexity: O(n * k), where n is the length of the array Space Complexity: O(1)

2. Optimal Approach (Reverse Method)

The optimal approach uses the reverse method to rotate the array in-place.

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

Solutions

Java Solution

// Brute Force Approach
class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        int temp, previous;
        for (int i = 0; i < k; i++) {
            previous = nums[nums.length - 1];
            for (int j = 0; j < nums.length; j++) {
                temp = nums[j];
                nums[j] = previous;
                previous = temp;
            }
        }
    }
}

// Optimal Approach (Reverse Method)
class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }

    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}

C++ Solution

// Brute Force Approach
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k %= nums.size();
        int temp, previous;
        for (int i = 0; i < k; i++) {
            previous = nums[nums.size() - 1];
            for (int j = 0; j < nums.size(); j++) {
                temp = nums[j];
                nums[j] = previous;
                previous = temp;
            }
        }
    }
};

// Optimal Approach (Reverse Method)
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k %= nums.size();
        reverse(nums, 0, nums.size() - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.size() - 1);
    }
private:
    void reverse(vector<int>& nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
};

Explanation

Brute Force Approach

  1. Iterate k times.
  2. In each iteration, move every element one step to the right.
  3. Move the last element to the first position.

This approach is simple but inefficient for large arrays and large values of k.

Optimal Approach (Reverse Method)

This approach uses the fact that when we rotate the array k times, the last k elements come to the front and the first n-k elements shift backwards.

  1. Reverse the entire array.
  2. Reverse the first k elements.
  3. Reverse the remaining n-k elements.

This method is efficient as it rotates the array in-place and has a time complexity of O(n).

Test Cases

  1. Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4] Explanation: The array is rotated 3 steps to the right.

  2. Input: nums = [-1,-100,3,99], k = 2 Output: [3,99,-1,-100] Explanation: The array is rotated 2 steps to the right.

  3. Input: nums = [1,2], k = 3 Output: [2,1] Explanation: k is larger than the array length, so it's equivalent to rotating 1 step (3 % 2 = 1).

These test cases cover scenarios with different array lengths, positive and negative numbers, and cases where k is larger than the array length.