Optimize rotation for in-place

Question

Find an efficient solution for rotation given the without recursion constraint.

Codemia · Accepted Answer

In this problem, we need to rotate an array in place without using additional space and without recursion. The problem can be analyzed using a technique known as 'reverse the segments'. The key observation is that rotating an array can be visualized as three reversals: first, reverse the entire array, then reverse the first 'k' elements, and finally, reverse the remaining elements. This approach is efficient and allows us to achieve the rotation in O(n) time and O(1) space.

1. **Reverse the entire array**: This step will put the elements that should be at the end of the array at the front. For example, if we have an array [1, 2, 3, 4, 5] and we want to rotate it by k=2, reversing gives us [5, 4, 3, 2, 1].

2. **Reverse the first k elements**: Next, we reverse the first k elements to restore their original order. Continuing our example, this would transform [5, 4, 3, 2, 1] back to [4, 5, 3, 2, 1].

3. **Reverse the remaining elements**: Finally, we reverse the remaining elements of the array to get the final rotated array. The last step gives us [4, 5, 1, 2, 3].

Thus, the array is rotated in place with minimal space usage.

Here is the Python code implementing the above approach:

```python
def rotate(nums, k):
    n = len(nums)
    k = k % n  # Handle cases where k > n

# 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 n-k elements
    reverse(k, n - 1)
```
This code effectively rotates the array in place.

The time complexity of this algorithm is O(n), where n is the length of the array. Each of the three reversal operations takes linear time. The space complexity is O(1) since we are only using a constant amount of extra space (for the pointers). This is optimal for in-place operations.

1. **k is zero**: When k=0, the array should remain unchanged. For example, rotating [1, 2, 3] by 0 results in [1, 2, 3].
2. **k is greater than the length of the array**: If k is larger than n, we use `k = k % n` to handle it. For instance, rotating [1, 2, 3] by 5 should yield [2, 3, 1].
3. **Empty array**: An empty array should remain empty regardless of k. For example, rotating [] by any number should still result in [].
4. **Single element**: An array with one element should remain unchanged. For instance, rotating [1] by 1 results in [1].

Optimize rotation for in-place

ServiceNow

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

ServiceNow 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