O(n) run time, O(1) space, rotating values in vector


  • 1
    L

    class Solution {
    public:
    void rotate(vector<int>& nums, int k) {
    int arrLen = nums.size();

        if (k >= arrLen){
            k = k % arrLen;
        }
        
        if (!arrLen){
            return;
        }
        
        if (k == 0){
            return;
        }
        
        int firstVal = nums[0];
        int firstIndex = 0;
    
        int emptyIndex = firstIndex;
            
        for (int i = 0; i < arrLen; i++){
            int correspondingIndex = (emptyIndex + arrLen - k) % arrLen;
            if (correspondingIndex == firstIndex){
                nums[emptyIndex] = firstVal;
                firstIndex++;
                firstVal = nums[firstIndex];
                emptyIndex = firstIndex;
            } else {
                nums[emptyIndex] = nums[correspondingIndex];
                emptyIndex = correspondingIndex;
            }
        }
    }
    

    };


  • 0
    J

    can you please explain how you came up with the equation
    correspondingIndex = (emptyIndex + arrLen - k) % arrLen ?
    thanks!


  • 0
    T

    It's actually correspondingIndex = emptyIndex - k (mod arrLen) adjusted to not be negative by going up one cycle with addition inside the modulo.


  • 0
    T

    Another way of looking at it, which probably answers jchiang1208's question better, is that the algorithm above rotates left by k if:
    correspondingIndex = emptyIndex + k (mod arrLen)
    or right by k if:
    correspondingIndex = emptyIndex - k (mod arrLen)
    which is the same as rotating left by arrLen - k:
    correspondingIndex = emptyIndex + (arrLen - k) (mod arrLen)


Log in to reply
 

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