Python version of O(1) space complexity code


  • -1
    K
    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.
            """
          # Naive solution - time complexity O(n) space complexity O(n) 
          #  copy = list(nums)
          #  for i in xrange(len(nums)):
          #     nums[(i+k)%len(nums)] = copy[i]
          
          # Efficient implementation
          # time complexity O(n) space complexity O(1)
            n = len(nums)    
            k = k % n 
            nums[:n-k] = nums[n-k-1::-1]
            nums[n-k:] = nums[n-1:n-k-1:-1]
            nums[:] = nums[::-1]

  • 0

    Array slicing in Python does not have O(1) complexity.


Log in to reply
 

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