Tutorial: Rotate Array Interview Question and Solution in Python

In this tutorial, we will dive into the popular coding interview question of rotating an array. Array rotation involves shifting the elements of an array to the left or right by a certain number of positions. This is a common problem that tests your ability to manipulate arrays efficiently. We will explore the problem statement, understand various approaches to solve it, and provide a detailed solution in Python.

Problem Statement

Given an array of integers and a positive integer k, rotate the array to the right by k steps. For example, if the array is [1, 2, 3, 4, 5, 6, 7] and k is 3, the array should be rotated to [5, 6, 7, 1, 2, 3, 4].

Here are a few examples to clarify the problem:

• Input: [1, 2, 3, 4, 5, 6, 7], k = 3
  Output: [5, 6, 7, 1, 2, 3, 4]
• Input: [-1, -100, 3, 99], k = 2
  Output: [3, 99, -1, -100]

Brute Force Approach

Before we dive into the optimal solutions, let’s explore a brute force approach to solving this problem. The idea is to repeatedly rotate the array by shifting each element to the right one by one, for a total of k rotations. This can be achieved through a simple loop.

Here’s a Python implementation of the brute force approach:

def rotate_brute_force(nums, k):
    n = len(nums)
    for _ in range(k):
        previous = nums[-1]
        for i in range(n):
            nums[i], previous = previous, nums[i]

While this approach is straightforward, it’s not the most efficient. The time complexity of this solution is O(n*k), where n is the length of the array and k is the number of rotations.

Using Extra Space

A more efficient approach involves using extra space to store the rotated array. We can calculate the new index of each element after rotation and store it in a new array.

Here’s how this approach works:

1. Calculate the new index for each element after rotation: new_index = (i + k) % n, where n is the length of the array.
2. Place each element in its new index in the rotated array.

Here’s the implementation in Python:

def rotate_extra_space(nums, k):
    n = len(nums)
    rotated = [0] * n
    for i in range(n):
        new_index = (i + k) % n
        rotated[new_index] = nums[i]
    return rotated

This approach has a time complexity of O(n) because we iterate through the entire array once to calculate the new indices and then copy the elements to the rotated array.

Reversing Subarrays

A clever approach that doesn’t require extra space involves reversing subarrays. The idea is to reverse the entire array, then reverse the first k elements, and finally reverse the remaining elements.

Here’s how this approach works:

1. Reverse the entire array.
2. Reverse the first k elements.
3. Reverse the remaining n - k elements.

This will result in the array being rotated by k positions to the right.

Let’s implement this approach in Python:

def reverse_subarrays(nums, start, end):
    while start < end:
        nums[start], nums[end] = nums[end], nums[start]
        start += 1
        end -= 1

def rotate_reverse(nums, k):
    n = len(nums)
    k %= n  # Handle cases where k is larger than n
    reverse_subarrays(nums, 0, n - 1)
    reverse_subarrays(nums, 0, k - 1)
    reverse_subarrays(nums, k, n - 1)

The time complexity of this approach is O(n), as we reverse subarrays three times.

Using Cyclic Replacements

Another efficient approach involves using cyclic replacements. In this approach, we place each element in its correct position in one cycle, and then move to the next element that hasn’t been placed yet. We continue this process until we’ve placed all elements in their correct positions.

Here’s how this approach works:

1. Start with an index start and an element current. Place the element at the new index next.
2. Calculate the new index next using the formula: next = (current + k) % n.
3. Swap the elements at indices start and next.
4. Update current to the value at index next.
5. Continue this process until you return to the original index start, which completes one cycle.
6. Move to the next index that hasn’t been placed and repeat the process.

Here’s the implementation in Python:

def rotate_cyclic(nums, k):
    n = len(nums)
    k %= n  # Handle cases where k is larger than n
    count = 0
    start = 0

    while count < n:
        current = start
        prev = nums[start]
        while True:
            next_index = (current + k) % n
            nums[next_index], prev = prev, nums[next_index]
            current = next_index
            count += 1
            if current == start:
                break
        start += 1

The time complexity of this approach is O(n), as we visit each element exactly once.

Summary

In this tutorial, we explored the problem of rotating an array in Python and discussed multiple approaches to solving it. We started with a brute force approach that involves shifting elements one by one, followed by an approach that uses extra space to store the rotated array. We then discussed a more efficient approach that involves reversing subarrays and an even more optimized approach using cyclic replacements.

Here’s a summary of the time complexities of the discussed approaches:

• Brute Force: O(n*k)
• Using Extra Space: O(n)
• Reversing Subarrays: O(n)
• Cyclic Replacements: O(n)

When faced with the array rotation problem in a coding interview, consider the constraints and choose the approach that best suits the requirements. The cyclic replacements approach, with its O(n) time complexity, is often a strong choice due to its efficiency and minimal memory usage.

Remember that practice is key to mastering coding interview questions. Try implementing these approaches on your own, experiment with different inputs, and analyze their performance. Happy coding!