Complete Python Explanation – 5 Methods
Let\'s start with one of the simplest ways of solving this problem \u2013\u2013 rotating nums by 1 step, a total of k times. From this solution, we can work tow
Let\'s start with one of the simplest ways of solving this problem \u2013\u2013 rotating ```nums``` by 1 step, a total of ```k``` times. From this solution, we can work towards better methods of solving the problem.\n\n**Method 1: Rotate 1 Step at a Time; Time: O(n\u2022k), Space: O(1) --> TLE**\n```\ndef rotate(self, nums: List[int], k: int) -> None:\n\tn = len(nums) # store length of nums\n\tfor _ in range(k):\n\t\tprev = nums[-1] # previous element starts as the end\n\t\tfor i in range(n):\n\t\t\tnums[i], prev = prev, nums[i] # this element becomes the previous one, store this element in prev\n```\nIn this solution, the inner part of our outer ```for``` loop rotates ```nums``` by one spot. We perform this operation ```k``` times to rotate by a total of ```k``` steps!\n\nThis solution takes ```O(n\u2022k)``` time where ```n == Ien(nums)``` since we need to look at every number in ```nums``` once to rotate by one step, and we do this ```k``` times. Unfortunately, this results in a time limit exception :( so instead of rotating one step at a time, let\'s try to rotate ```k``` steps at a time using a second array for extra storage!\n\nTo come up with this solution, we need to think more about how rotation actually works. First, let\'s think about what happens if ```nums``` has length ```5``` and we rotate ```5``` times. By the time we\'ve made our fifth rotation, ```nums``` will be back in its original orientation! Similarly, if we rotate ```6``` times, then the first ```5``` rotations won\'t do anything so it\'s the same as rotating just once! Essentially, rotating ```k``` times is the same as rotating ```k % n``` times! \n\nSecondly, if we are rotating ```3``` times, then the last three elements in ```nums``` are going to end up going to the beginning of the array! This means that we need to be careful that we don\'t accidentally try to insert any elements into indices beyond the end of ```nums```.\n\nWith this knowledge we can realize that an element at index ```i``` will need to be at index ```(i + k) % n``` after our rotation! So we can use our second array to simply set every element in ```nums``` to be their new value.\n\n**Method 2: Copy Array; Time: O(n), Space; O(n)**\n```\ndef rotate(self, nums: List[int], k: int) -> None:\n\tcopy = [num for num in nums] # copy the nums array\n\tn = len(nums)\n\tfor i, num in enumerate(copy): # for every element in the copy\n\t\tnums[(i + k) % n] = copy[i] # set corresponding location in nums\n```\n(P.S. ```for i, num in enumerate(copy)``` is the same as using ```for i in range(n)``` and then saying ```num = copy[i]```)\n\nSince we made a copy of our original array, the space complexity is ```O(n)```. The time this solution takes scales directly with the number of elements, so it is ```O(n)```. This is a great solution and gets accepted, but we can still improve! \n\nEarlier we went over what happens if we rotate ```3``` times in an array of length ```5``` \u2013 the last ```3``` elements get rotated to the front. This means that ```nums``` will become ```[last three elements] + [first two elements]```. In python syntax, this is ```nums[-3:] + nums[-3:]``` (the negative index is the same as using ```n-3```). Therefore, we want ```nums = nums[-k:] + nums[:-k]```! However, there are two important things to note. \n\nFirst, we need to remember that ```k``` can be bigger than ```n```! To avoid trying to index the ```-10```th element of an array of length ```5``` (in a hypothetical case where ```n = 5``` and ```k = 10```), we can use our mod operator from before \u2013\u2013 we really want ```nums = nums[-k%n:] + nums[:-k%n]```. To fix this we can just add ```k %= n``` at the beginning of our answer (this is the same as ```k = k % n```).\n\nSecond, if we set ```nums = nums[-k:] + nums[:-k]```, then we will actually be creating a new pointer for ```nums``` in memory. Since we want to actually set ```nums``` to this result, we need to set ```nums[:] = nums[-k:] + nums[:-k]```, which will overwrite ```nums``` element by element.\n\n**Method 3: Pythonic; Time: O(n), Space: O(n)**\n```\ndef rotate(self, nums: List[int], k: int) -> None:\n\tn = len(nums) # store length\n\tk %= n # avoid unnecessary rotations\n\tnums[:] = nums[-k:] + nums[:-k] # set nums to answer\n```\nThis can also be turned into a one-liner:\n```\ndef rotate(self, nums: List[int], k: int) -> None:\n\tnums[:] = nums[-k%len(nums):] + nums[:-k%len(nums)]\n```\nThis solution also takes ```O(n)``` time and space since we still look at every element once and we also need extra space temporarily for ```nums[-k:]``` and ```nums[:-k]```. This is a very pythonic solution, but since we know the order that the elements in ```nums``` will end up, we can optimize our space storage from ```O(n)``` to ```O(k)``` by just storing the last ```k``` elements of ```nums``` and shifting the first ```n-k``` manually.\n\n**Method 4: Store last k elements; Time: O(n), Space: O(k)**\n```\ndef rotate(self, nums: List[int], k: int) -> None:\n\tn = len(nums)\n\tk %= n\n\tif k != 0: # we only want to rotate the array if we need to\n\t\tend = nums[-k:] # store the end of the array (which will become the front)\n\t\tfor i in range(n-k-1, -1, -1): # go backwards through the first n-k elements of the array\n\t\t\tnums[i+k] = nums[i] # shift everything forward k spots\n\t\tnums[:k] = end # put the old end to the front\n```\nThe key to this solution is that we have to iterate backwards through ```nums``` with our ```for i in range(n-k-1, -1, -1)``` loop since otherwise, we may overwrite future values that we need!\n\nThis solution still takes ```O(n)``` time but now takes just ```O(k)``` space! We can actually optimize this depending on whether or not the end or beginning of our array is smaller:\n\n```\ndef rotate(self, nums: List[int], k: int) -> None:\n\tn = len(nums)\n\tk %= n\n\tif k != 0: # we only want to rotate the array if we need to\n\t\tif k < n//2: # if the end is less than half the size of the array\n\t\t\tend = nums[-k:] # store the end of the array (which will become the front)\n\t\t\tfor i in range(n-k-1, -1, -1): # go backwards through the first n-k elements of the array\n\t\t\t\tnums[i+k] = nums[i] # shift everything forward k spots\n\t\t\tnums[:k] = end # put the old end to the front\n\t\telse: # the end is bigger than the beginning so store the beginning\n\t\t\tbeg = nums[:-k] # store the beginning!\n\t\t\tfor i in range(n-k, n): # go forwards through the last k elements\n\t\t\t\tnums[(i+k)%n] = nums[i] # shift them forwards k spots (to the front of the list)\n\t\t\tnums[k:] = beg # set the end to the beginning\n```\nThis makes the space complexity ```O(min(k, n-k))```.\n\nThis is a great solution but crazily there is one way to reduce the space complexity further! To do this, we need a special insight about how to rotate the array. We want the last ```k``` elements to become the first ```k``` elements of our array, so how about we begin by reversing the whole list. After that, the first ```k``` elements will be last ```k``` elements of our original list, but they will be in reverse order. Similarly, the new end of our list will be the old beginning, only in reverse order. So how do we remedy this? Well, we can reverse the first ```k``` elements of our new array and the last ```n-k``` elements! After that, the array will be fully rotated!\n\n**Method 5: Reverse; Time: O(n), Space: O(1)**\n```\ndef rotate(self, nums: List[int], k: int) -> None:\n\tdef reverse(start, end): # helper method to reverse from start to end\n\t\twhile start < end: # while there is stuff to reverse\n\t\t\tnums[start], nums[end] = nums[end], nums[start] # swap the elements at the ends\n\t\t\tstart, end = start + 1, end - 1 # move pointers closer to each other\n\t\t\t\n\tn = len(nums)\n\tk %= n\n\treverse(0,n-1) # reverse full list\n\treverse(0,k-1) # reverse first k elements (previously the last k elements)\n\treverse(k,n-1) # reverse the rest of the list\n```\n\nIf you are still confused about how this works, I\'ll show what ```nums``` looks like after each step with the example problems:\n\n***Example 1***\n```\noriginal nums: [1, 2, 3, 4, 5, 6, 7]\nnums after fully reversing: [7, 6, 5, 4, 3, 2, 1]\nnums after reversing the first k elements: [5, 6, 7, 4, 3, 2, 1]\nnums after reversing the remaining elements: [5, 6, 7, 1, 2, 3, 4]\n```\n\n***Example 2***\n```\noriginal nums: [-1, -100, 3, 99]\nnums after fully reversing: [99, 3, -100, -1]\nnums after reversing the first k elements: [3, 99, -100, -1]\nnums after reversing the remaining elements: [3, 99, -1, -100]\n```\n\n**Thanks for Reading!**\nPlease consider upvoting the post if it helped you! If you have any questions, comments, or concerns, please leave them below and I will get to them as soon as possible.
['Python']