Leetcode 189. Rotate Array
Explanation for Leetcode 189 - Rotate Array, and its solution in Python.
Problem
Example:
1
2
3
4
5
6
7
8
9
10
11
12
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]
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]
Approach
First we want to get k modulo len(nums) because if k = len(nums) then that’s just rotating array len(nums) times which is the same as rotating 0 times.
Once we look at our expected output, we can find that that it’s separated into two parts.
For example, with nums = [1,2,3,4,5,6,7], our expected output = [5,6,7,1,2,3,4]. As you can it’s segragated into 2 parts from 0 to k-1 [5,6,7] and k to len(nums) [1,2,3,4].
We can also see when we reverse an array, it becomes [7,6,5,4,3,2,1] and we find a similiarity where we simply have to reverse from 0 to k-1 and k to len(nums) and would result in expected output
Visualization of the Approach:
1
2
3
4
5
6
7
8
9
10
11
12
nums = [1,2,3,4,5,6,7], k = 3
k = k%(len(nums)) = 3
After reversing whole nums
nums = [7,6,5,4,3,2,1]
After reversing 0 to k-1
nums = [5,6,7,4,3,2,1]
After reversing k to len(nums)-1
nums = [5,6,7,1,2,3,4]
Here is the Python code for the solution:
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
def reverse(left, right):
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
k = k % len(nums)
reverse(0, len(nums)-1)
reverse(0, k-1)
reverse(k, len(nums)-1)
Time Complexity and Space Complexity
Time Complexity: $O(n)$
Space Complexity: $O(1)$