Optimize rotation for in-place

Question

Given an array of integers, rotate the array in-place to the right by a specified number of steps. The rotation should be done without using extra space, and the function should modify the original array. For example, given the input array [1, 2, 3, 4, 5] and k = 2, the output should be [4, 5, 1, 2, 3].

Codemia · Accepted Answer

The problem requires us to rotate an array in-place, which means we cannot use additional data structures that would consume extra space. This is a classic example of a problem that can be solved using the **reverse** technique, rather than utilizing a sliding window or two pointers directly. The reverse technique allows us to achieve the desired rotation in three steps: reverse the entire array, reverse the first 'k' elements, and then reverse the remaining elements. This approach is efficient and fits the constraints of the problem perfectly.

To rotate the array to the right by 'k' steps:
1. **Normalize k:** Since rotating an array of length n by k steps is equivalent to rotating it by `k % n` steps, we first handle cases where k is greater than n.
2. **Reverse the entire array:** This will place the elements that need to move to the front at the back of the array.
3. **Reverse the first k elements:** This will correctly position the rotated elements at the beginning of the array.
4. **Reverse the remaining n-k elements:** This will position the rest of the elements correctly.

For example, given the input array [1, 2, 3, 4, 5] and k = 2:
- Normalize k: k = 2 % 5 = 2
- Step 1: Reverse entire array -> [5, 4, 3, 2, 1]
- Step 2: Reverse first k elements -> [4, 5, 3, 2, 1]
- Step 3: Reverse remaining elements -> [4, 5, 1, 2, 3]

Here is the Python solution implementing the approach discussed:
```python
def rotate(nums, k):
    n = len(nums)
    k = k % n  # Normalize k
    if k == 0:
        return  # No rotation needed

# Helper function to reverse a portion of the array
    def reverse(start, end):
        while start < end:
            nums[start], nums[end] = nums[end], nums[start]
            start += 1
            end -= 1

# Step 1: Reverse the entire array
    reverse(0, n - 1)
    # Step 2: Reverse the first k elements
    reverse(0, k - 1)
    # Step 3: Reverse the remaining elements
    reverse(k, n - 1)
```
This solution modifies the original array in-place as required.

The time complexity of this solution is O(n) because we are traversing the array a constant number of times (three reversals). The space complexity is O(1) since we are not using any additional data structures that grow with input size, only a few variables for indices. This meets the problem's requirement of in-place modification.

1. **k = 0:** If k is zero, the array should remain unchanged. For example, `rotate([1, 2, 3], 0)` should return `[1, 2, 3]`.
2. **k greater than array length:** If k is greater than the length of the array, it should be normalized. For instance, `rotate([1, 2, 3, 4, 5], 7)` should effectively rotate by 2 steps, resulting in `[4, 5, 1, 2, 3]`.
3. **Empty array:** An empty array should not throw an error and should remain empty. `rotate([], 3)` should return `[]`.
4. **Array of length 1:** An array with a single element should also remain unchanged regardless of k, e.g., `rotate([1], 10)` should return `[1]`.

Optimize rotation for in-place

Elastic

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Elastic Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string