Interesting O(n) time O(1) space solution without Swap() with detailed comments


  • 0
    L

    //Time complexity O(n), extra space cost O(1)

    public class Solution {
        public void rotate(int[] nums, int k) {
            k %= nums.length;
            if(k<=0) return;
            int index = k, loopHead = 0, curr = nums[0];
            //1. index is the index of the element we will update in each iteration. 
            //2. loopHead is head of a loop (if exist) for index since each time we
            // move index k steps further.
            //3. curr is the value got from previous iteration nums[preIndex] and 
            //for updating nums[index]
            for(int count=0;count<nums.length;count++){
                if(index==loopHead){ //loop detected
                    nums[index] = curr; //set the value of loopHead.
                    loopHead++; //move 1 step further to jump out of loop
                    curr = nums[++index]; //This is the head of new loop
                    index = (index+k)%nums.length;
                }
                else{ //each time go k steps further
                    int tmp = nums[index];
                    nums[index] = curr;
                    curr = tmp;
                    index = (index+k)%nums.length;
                }
            }
        }
    }

  • 0
    W

    Thanks for sharing! It's interesting.


  • 0
    R

    {
    int tmp = nums[index];
    nums[index] = curr;
    curr = tmp;
    } this is just swap(). why do you say that " O(1) space without Swap()" ?


  • 0
    L

    Hi rabbitlxf, I mean I didn't swap between two elements compared to other's solution using swap between two elements, in each step, I just set i+k th element to the value of i th element and didn't set ith element to the value of i+k th element. For example the array is [3,4,7,2] and k = 1, my solution did it in the following order: Set Array[1] = 3, Array[2] =4, Array[3] = 7, Array[0] = 2. Surely you could just treat it as swap among N elements. For the O(1) space complexity, clearly it's O(1), since the extra tmp variable is only alive in one iteration of for loop. Or you can put it outside the for loop.


Log in to reply
 

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