Question

• https://leetcode.com/problems/rotate-array/

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

Could you do it in-place with O(1) extra space?

Approach

• There will be cycles of k, the error is for cases where k is not multiple of n. Ex : [1,2,3,4,5,6,7] with k=3. Sol ->

    class Solution {
         public void rotate(int[] nums, int k) {
           k = k % nums.length;
           int count = 0;
           for (int start = 0; count < nums.length; start++) {
             int current = start;
             int prev = nums[start];
             do {
               int next = (current + k) % nums.length;
               int temp = nums[next];
               nums[next] = prev;
               prev = temp;
               current = next;
               count++;
             } while (start != current);
           }
         }
       }
  

• Reverse the array and then reverse back k and n-k elements.

Solution

public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k = k%n;
        for(int i=0; i<n/2; i++) {
            int temp = nums[i];
            nums[i] = nums[n-i-1];
            nums[n-1-i] = temp;
        }
        for(int i=0; i<k/2; i++) {
            int temp = nums[i];
            nums[i] = nums[k-i-1];
            nums[k-1-i] = temp;
        }
        for(int i=0; i<(n-k)/2; i++) {
            int temp = nums[k+i];
            nums[k+i] = nums[n-i-1];
            nums[n-1-i] = temp;
        }
    }
};