Rotate array LeetCode

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:

Rotate array
Rotate array

Problem statement

Given an array of integers called nums, rotate the array to the right by k elements, where k is positive.

Constraints

  • 11 \leqnums.length 105\leq10^5

  • 231-2^{31} \leqnums[i] 2311\leq 2^{31} - 1

  • 00 \leqk 105\leq10^5

Let’s map our previous example to the problem for better understanding.

Rotate array
Rotate array
1 of 3

There may be a case when k is equal to the length of the nums.

Rotate array
Rotate array
1 of 5

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.

Knowledge test

Now that we have understood the problem, let’s check our knowledge by rotating the array shown in the example below:

Knowledge test
Knowledge test

Algorithm

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:

  1. Initialize two pointers, start and end, which point to the 0th and last indices of the array.

  2. Swap the elements of start and end pointers.

  3. Increment start by11, and decrement end by11.

  4. Repeat the step 22 and 33 until the start becomes equal to the end.

Let’s visualize how to reverse the array elements:

Reverse an array
Reverse an array
1 of 6

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:

  1. Check if the nums is empty, or if k is 0. If so, return the original array since no rotation can be performed.

  2. Normalize k to minimize the rotation; that is if the length of the nums is77, and the value of k is1717, we will take the modulus of k with the length of the nums to make it33.

  3. Perform the following rotations:

    1. Reverse all the elements of the original array.

    2. Reverse the elements from 0 to k - 1.

    3. 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.

Rotate array
Rotate array
1 of 3

Coding example

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 end
def reverse(nums, start, end):
# Start a loop which will run as long as start is less than end
while start < end:
# Swap the elements at position start and end
nums[start], nums[end] = nums[end], nums[start]
# Increment the start by 1
start += 1
# Decrement the end by 1
end -= 1
# Function to rotate the array
def 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 rotation
k = k % n
# Reverse the entire array
reverse(nums, 0, n - 1)
# Reverse the elements from index 0 to k - 1
reverse(nums, 0, k - 1)
# Reverse the elements from index k to n - 1
reverse(nums, k, n - 1)
# Driver code
if __name__ == "__main__":
nums = [1, 2, 3, 4, 5]
k = 2
print("Original Array:", nums)
rotate_array(nums, k)
print("Rotated Array:", nums)
Rotate array

Now that we have a solution for this LeetCode problem, let’s analyze its time and space complexity.

Time 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 O(N+N+N)O(N+N+N)time complexity, which is O(N)O(N).

Space complexity

In this approach, we reverse the array in place, which does not require additional space. The space complexity for this algorithm would beO(1)O(1).

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved