Simple c++ solution with detail explain and O(1) extra space

  • 12
     * this solution is so-called three times rotate method
     * because (X^TY^T)^T = YX, so we can perform rotate operation three times to get the result
     * obviously, the algorithm consumes O(1) space and O(n) time
    class Solution {
        void rotate(int nums[], int n, int k) {
            k %= n; // if k > n then the final result is the same as k%n
            reverseArray(nums, n-k, n-1);
            reverseArray(nums, 0, n-k-1);
            reverseArray(nums, 0, n-1);
         * rotate the array nums from start to end
        void reverseArray(int nums[],int start, int end){
            while(start < end){
                int temp = nums[start];
                nums[start++] = nums[end];
                nums[end--] = temp;
                // or you can simply code as "std::swap(nums[start++], nums[end--])" to replace above three lines

  • 0

    Though there's one more elegant solution. I still like your way. It's straight and simple enough for normal people like me to understand.

  • 0

    Nice explanation, I like the name so-called three rotation method, and it takes exactly n operations, should be best performance algo from my understanding.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.