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:

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:

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 by $1$ , and decrement end by $1$ .
Repeat the step $2$ and $3$ until the 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 is $7$ , and the value of k is $17$ , we will take the modulus of k with the length of the nums to make it $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.

# 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)$ time complexity, which is $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 be $O(1)$ .

Rotate array LeetCode

Problem statement

Knowledge test

Algorithm

Coding example

Time complexity

Space complexity