Leetcode Study Day 4

Rotate Array

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 <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105

My solution

My solution is actually very simple, I make a for loop to run k times. In this loop, I push all elements to a new array but make their index number plus 1. Then I replace the first element with the last element.
This method is not very efficient, and face the Time Limit Exceeded problem.

Reverse Method (Optimized):

Accroding to ChatGPT, the approach of reversing the array multiple times to achieve rotation is a well-known and clever technique that comes from a deeper understanding of how array rotations work. The code is very simple but it’s hard to relate reversation to this problem.

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n; // Handle cases where k is greater than n

        if (k == 0) {
            return; // No need to rotate if k is 0
        }

        reverse(nums.begin(), nums.end()); // Reverse the entire array
        reverse(nums.begin(), nums.begin() + k); // Reverse the first k elements
        reverse(nums.begin() + k, nums.end()); // Reverse the remaining elements
    }
};

From this solution, I learn that if k, which is the rotation time can mod n, i.e., k % n = 0, there is no need to rotate the array. Then we only need to reverse the whole array first, then reverse the first k element first, then reverse the rest element first. This solution is related to math, and it’s very efficient.

Using Cyclic Replacements:

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n; // Handle cases where k is greater than n

        if (k == 0) {
            return; // No need to rotate if k is 0
        }

        int count = 0; // Count of elements processed
        int start = 0; // Start position for each cycle

        while (count < n) {
            int current = start;
            int prev = nums[start];

            do {
                int next = (current + k) % n;
                int temp = nums[next];
                nums[next] = prev;
                prev = temp;
                current = next;
                count++;
            } while (start != current);

            start++; // Move to the next cycle
        }
    }
};

I actually can’t get this idea, maybe leave it later…

Using Extra Array (Space-Optimized):

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n; // Handle cases where k is greater than n

        if (k == 0) {
            return; // No need to rotate if k is 0
        }

        vector<int> rotated(n); // Create an extra array

        for (int i = 0; i < n; i++) {
            rotated[(i + k) % n] = nums[i]; // Copy elements to their rotated positions
        }

        nums = rotated; // Copy the rotated array back to the original array
    }
};

This solution is easier to understand. The main idea is to create a new array to store the rotated array. Then we copy the elements to their rotated positions. Finally, we copy the rotated array back to the original array. One thing that i need to understand is that we can use mod to get the rotated position of each element.