[Java] O(n) time, O(1) memory, using Euclidean algorithm


  • 0
    S
    public class Solution {
        public void rotate(int[] nums, int k) {
            int n = nums.length;
            if (n == 0) return;
            
            k = k % n;
            if (k == 0) return;
            
            int gcd = gcd(n, k);
            
            // Do 'gcd' times rotation to the right
            // Each element will be touched only once -> O(n) time complexity
            for (int i = 0; i < gcd; i++) {
                // Remember last element
                int lastIndex = n-1 - i;
                int last = nums[lastIndex];
                
                // Rotate right
                int j = lastIndex - k;
                while (j != lastIndex) {
                    nums[(j + k) % n] = nums[j];
                    j = (j - k + n) % n;
                }
                
                // Replace first element with last element
                nums[(lastIndex + k) % n] = last;
            }
        }
        
        // Greatest common divisor
        int gcd(int a, int b) {
            if (b > a) return gcd(b, a);
            // a >= b
            if (a % b == 0) return b;
            return gcd(b, a%b);
        }
    }

  • 0
    S

    Wow, nice algorithm. Can I know why rotate 'gcd' times?


  • 0
    B

    you can try [1,2,3,4,5,6] , k =2. And you will know why you need 'gcd' times.


Log in to reply
 

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