Given an array, rotate the array to the right by k steps, where k is non-negative.
Follow up:
Example 1:
Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4] Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] rotate 3 steps to the right: [5,6,7,1,2,3,4]
Example 2:
Input: nums = [-1,-100,3,99], k = 2 Output: [3,99,-1,-100] Explanation: rotate 1 steps to the right: [99,-1,-100,3] rotate 2 steps to the right: [3,99,-1,-100]
Constraints:
1 <= nums.length <= 2 * 10^4-2^31 <= nums[i] <= 2^31 - 10 <= k <= 10^5
The description was taken from https://leetcode.com/problems/rotate-array/.
#O(N) Time, O(1) Space
class Solution:
def rotate(self, nums:list, k:int) -> None:
def reverse(left:int, right:int) -> None:
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
k %= len(nums)
reverse(0, len(nums)-1)
reverse(0, k-1)
reverse(k, len(nums)-1)A couple of approaches that may come to mind right away to solve this problem would be to create two arrays and then flip/merge them or to pop off the k values and insert them onto the beginning. The first approach would be linear time and space. The second approach would be quadratic time and linear space.
We can solve this problem with a trick that will yield linear time and constant space.
This can be achieved by reversing the entire array, reversing the zero through k indices, and then reversing the indices from k to the end of the list.
Let's start by creating our reverse function.
The function will take a left integer pointing at the beginning of the subarray we want to reverse, and a right integer pointing at the end.
def reverse(nums:list[int], left:int, right:int) -> None
While the left and right pointers haven't met each other, we will swap the left and right values.
We will move the pointers inward and continue until all the input values have been reversed.
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
We will then modulo k by the length of the input array.
We want to do this because if we get a k value that is greater than the size of our array then we will get an index out of bounds error when we use the swapping method within our reverse function, not to mention an entire rotation the length of the array will result in the same array so we can avoid any unnecessary traversals.
k %= len(nums)
Now that we have our reverse function made, and our appropriate k value, we will begin our magic.
Let's take this test case as an example:
nums = [1,2,3,4,5,6,7] k = 3
We will the initial reverse function of the entire array, making it:
[7,6,5,4,3,2,1]
reverse(0, len(nums)-1)
We will then reverse the beginning numbers up until k (minus one because array indexing starts at zero), making our array:
[5,6,7,4,3,2,1]
reverse(0, k-1)
Finally, we will reverse the numbers from k to the end of the array, making our array:
[5,6,7,1,2,3,4]
reverse(k, len(nums)-1)