Python O(1) space and O(n) time solution


  • 1
    Z

    For each element at position i, we need to move them to (i + k) % n, use a buffer to save the element that has been replaced, and move the replaced element to its right place.
    We will start from an element, and mark that, if we come back to the starting point, means we need to start over from the element next of the current starting point.
    Work terminates when we have move exactly n times.

    Example:
    Input:
    [1,2,3,4,5,6]
    2

    Process:

    1. startIdx = 0
      1, [1,2,3,4,5,6] -> 3, [1,2,1,4,5,6] -> 5, [1,2,1,4,3,6] -> [5,2,1,4,3,6]

    2. startIdx = 1
      2, [5,2,1,4,3,6] -> 4, [5,2,1,2,3,6] -> 6, [5,2,1,2,3,4] -> [5,6,1,2,3,4]

    class Solution(object):
        def rotate(self, nums, k):
            """
            :type nums: List[int]
            :type k: int
            :rtype: void Do not return anything, modify nums in-place instead.
            """
            if k == 0:
                return
            
            n = len(nums)
            k = k % n
            
            moves = 0
            idx = 0
            buff, startIdx = nums[idx], idx
            
            # need total of n moves to complete
            while moves < n:
                # where the current buffered element should move to
                idx = (idx + k) % n
                nums[idx], buff, moves = buff, nums[idx], moves + 1
                
                # we have come back to the start idx, move to process next element
                if idx == startIdx:
                    idx += 1
                    if idx >= n:
                        break
                    buff, startIdx = nums[idx], idx
    

  • 0
    M

    @zhanchch

    I appreciate your solution - I got stuck on the early loop part for a bit myself (wherein the length of the list is an integer multiple of k) and I now understand the logic for handling that!

    One suggestion: remove the if idx >= n: check - it appears to be superfluous no matter what.

    As that last loop check is always hit at least once per list (whether it is needed or not), I thought a check would save a few CPU cycles, so I added it below.

    I also have the k==0 check where it can catch k=x*n where x > 0.

    class Solution(object):
        def rotate(self, nums, k):
            """
            :type nums: List[int]
            :type k: int
            :rtype: void Do not return anything, modify nums in-place instead.
            """
            n = len(nums)
            k %= n
            if k == 0:
                return
            idx = 0
            init_idx = idx
            temp = nums[init_idx]
            for step in xrange(n):
                idx = (idx+k)%n
                nums[idx], temp = temp, nums[idx]
                if idx == init_idx:  # may have hit a cycle so inc idx
                    if step >= n-1:
                        break  # we're already done!
                    idx += 1
                    init_idx = idx
                    temp = nums[idx]
    

Log in to reply
 

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