Rotating an array is a classic computer science problem that involves shifting the elements of an array to the right by a specified number. The LeetCode Rotate Array problem focuses on array manipulation techniques used in various domains, such as data processing, data encryption, computer graphics, and image processing. Let us consider an example of the rotate array:
Given an array of integers called nums
, rotate the array to the right by k
elements, where k
is positive.
Constraints
nums.length
nums[i]
k
Let’s map our previous example to the problem for better understanding.
There may be a case when k
is equal to the length of the nums
.
When the value of k
equals the length of nums
, we can see that the resulting array will be the same as the original array. So, we won’t be able to perform any rotation in this case.
Now that we have understood the problem, let’s check our knowledge by rotating the array shown in the example below:
The algorithm reverses the array multiple times to rotate the array. Before discussing the algorithm for rotating the array, let us discuss how array reversal works.
Reversing the array uses a two-pointer technique to traverse the array from both ends. Here is how the array reversal works:
Initialize two pointers, start
and end
, which point to the 0th and last indices of the array.
Swap the elements of start
and end
pointers.
Increment start
byend
by
Repeat the step start
becomes equal to the end
.
Let’s visualize how to reverse the array elements:
Let us now understand the algorithm. We will reverse the array in place using the above-mentioned algorithm to rotate without consuming any space.
Here’s how this approach works:
Check if the nums
is empty, or if k
is 0. If so, return the original array since no rotation can be performed.
Normalize k
to minimize the rotation; that is if the length of the nums
isk
isk
with the length of the nums
to make it
Perform the following rotations:
Reverse all the elements of the original array.
Reverse the elements from 0
to k - 1
.
Reverse the elements from k
to n - 1
, where n
is the array’s length.
Let’s visualize how to reverse the array elements to rotate the array by k
elements:
Note: For the following example, the value of k
is 3.
Let’s take a look at the code for the algorithm we just discussed:
# Function to reverse elements in the array from index start to enddef reverse(nums, start, end):# Start a loop which will run as long as start is less than endwhile start < end:# Swap the elements at position start and endnums[start], nums[end] = nums[end], nums[start]# Increment the start by 1start += 1# Decrement the end by 1end -= 1# Function to rotate the arraydef rotate_array(nums, k):n = len(nums)# Check if nums is empty or if k is 0. No rotation will be performed in this case and we will simply return.if n == 0 or k == 0:return# Normalize k to minimize rotationk = k % n# Reverse the entire arrayreverse(nums, 0, n - 1)# Reverse the elements from index 0 to k - 1reverse(nums, 0, k - 1)# Reverse the elements from index k to n - 1reverse(nums, k, n - 1)# Driver codeif __name__ == "__main__":nums = [1, 2, 3, 4, 5]k = 2print("Original Array:", nums)rotate_array(nums, k)print("Rotated Array:", nums)
Now that we have a solution for this LeetCode problem, let’s analyze its time and space complexity.
In this algorithm, we reverse the array three times. In the worst case, we must traverse the entire array three times. Traversing the array three times will lead to an
In this approach, we reverse the array in place, which does not require additional space. The space complexity for this algorithm would be
Free Resources