Rotate Array by K Positions

Array rotation is a classic algorithm problem where we need to shift array elements by k positions. The optimal approach uses the reversal technique to achieve O(1) space complexity while maintaining O(n) time efficiency.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. What are the constraints on array size? (e.g., is it bounded by Integer.MAX_VALUE?)
2. Can we mutate the input array in-place, or do we need to return a new array?
3. Should we handle negative rotation values (i.e., rotate left instead of right)?
4. What's the expected time complexity? (e.g., O(n) or better?)
5. Are there any specific edge cases we should consider, like empty arrays or rotation count equal to array length?

Restated problem in my own words: Given an integer array and a number of positions to rotate, we need to shift all elements to the right by that many positions. Elements that "fall off" the right end should reappear at the left end.

Clarified inputs, outputs, and constraints:

• Input: An integer array nums of length n (0 ≤ n ≤ 10⁵) and an integer k representing rotation count
• Output: The same array rotated right by k positions (or a new array if in-place mutation isn't allowed)
• Constraints:
  • k can be any integer (including negative values)
  • Array elements are integers in typical range
  • We should handle edge cases like empty arrays gracefully

Assumptions I'm making:

• The rotation count k can be larger than the array length, so we should use modulo arithmetic to reduce it
• We can mutate the input array in-place for efficiency (as is typical in FAANG problems)
• Negative rotation values mean left rotation, which we can handle by converting to equivalent right rotation

Data shape and hidden structure: The problem has a cyclic nature where elements form a circular shift pattern. The array can be viewed as having two segments that get swapped when rotated: the last k elements and the first (n-k) elements. This suggests we might be able to solve it using reversal operations or modular arithmetic.

The key insight is that rotation by k positions is equivalent to taking the last k elements and placing them at the beginning, or equivalently, taking the first (n-k) elements and moving them to the end. This structure enables us to think about reversal-based approaches or mathematical modular indexing.

2. Pattern Recognition

Identifying the most likely pattern or patterns

The most likely pattern for this problem is array rotation with reversal technique. This is a classic array manipulation problem that can be solved efficiently using the three-step reversal algorithm.

Wording that signals the pattern

The key phrases that signal this pattern:

• "rotate array" - immediately suggests shifting elements in a circular manner
• "k positions" - indicates a fixed rotation amount that can be handled with mathematical approach rather than iterative shifting
• "in-place" - suggests we should avoid using extra space beyond O(1) for the solution

Why this problem fits that pattern

This problem fits the reversal pattern because:

1. It's a classic array rotation problem where elements need to be shifted in a circular fashion
2. The optimal solution uses the mathematical property that rotating an array by k positions can be achieved through three reversals
3. The pattern leverages the fact that we can break down the rotation into manageable subproblems using reversal operations

Core insight needed to solve it

The core insight is that rotating an array by k positions can be achieved by:

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

This works because reversing creates a "mirror" effect that effectively moves elements to their correct rotated positions, and the mathematical property of reversals allows us to achieve this in O(1) space and O(n) time.

This pattern is particularly powerful because it transforms what appears to be an O(nk) problem into an O(n) solution through clever mathematical manipulation of array operations.

3. Approach Evolution

My first instinct is to think about a brute force approach where I rotate the array one position at a time, but that would be O(n×k) where k is the number of rotations, which could be up to n. That's inefficient because it would result in O(n²) time complexity in the worst case.

Let me think about how to optimize this. I notice that if I reverse the entire array first, then reverse the first k elements and finally reverse the remaining elements, I can achieve the rotation in O(n) time with O(1) extra space. This is a classic three-step reversal technique.

The key insight here is that rotation can be decomposed into three reversals:

1. Reverse the entire array
2. Reverse the first k elements (where k = k % n)
3. Reverse the remaining elements from position k onwards

This approach works because when we reverse the entire array, we effectively move all elements to their new positions in reverse order. Then by reversing specific segments, we can get the desired final arrangement.

Let me trace through this more carefully. If we have array [1,2,3,4,5,6,7] and need to rotate right by 3 positions:

• Step 1: Reverse entire array → [7,6,5,4,3,2,1]
• Step 2: Reverse first 3 elements → [5,6,7,4,3,2,1]
• Step 3: Reverse remaining elements from index 3 onwards → [5,6,7,1,2,3,4]

This gives us the correct result. The invariant that must hold is that we're maintaining the relative order of elements within each segment while placing them in their correct final positions.

The approach is optimal because:

1. It's O(n) time complexity - we make exactly 3 passes through the array
2. It's O(1) space complexity - we only use a constant amount of extra variables
3. It's in-place - no additional array allocation needed

This is much better than the naive O(n²) approach where we'd need to shift elements one by one for each rotation step.

4. Data Structure Choice

For the rotate array problem, I'll use a combination of primitive arrays and integer indices to achieve an optimal in-place solution.

Primary Data Structures:

• int[] nums: The input array that needs to be rotated in-place
• int k: The rotation count (normalized to handle cases where k > nums.length)

Why Each Data Structure Is Needed:

• The int[] nums array is essential because we must modify the input array in-place as required by the problem constraints. We cannot create a new array of size n, which would simplify the solution but violate the in-place requirement.
• The int k variable is needed to store the rotation count, which must be normalized modulo the array length to handle cases where k exceeds the array size.

Time and Space Impact:

• Time Complexity: O(1) for all operations since we only use a fixed number of integer variables and array access
• Space Complexity: O(1) extra space, as we only use a constant number of additional variables (the temporary variable for swapping and the index tracking variables)

Helper Structure:

• No additional helper data structures: The solution uses only the input array and a few integer variables. We don't need hash maps, stacks, or queues because the rotation can be handled with simple index arithmetic and in-place swapping.

The approach avoids any additional space complexity beyond what's required for the algorithm's working variables, making it optimal in terms of space usage. The solution leverages array indexing and modular arithmetic to handle the rotation efficiently without requiring additional memory structures.

// The solution uses only the input array and a few integer variables
// No additional data structures like stacks, queues, or hash maps are needed

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to demonstrate how it works step by step.

Example: nums = [1,2,3,4,5,6,7], k = 3

Step 1: Normalize k to handle cases where k > nums.length

• k = 3 % 7 = 3 (no change needed)

Step 2: Reverse entire array

• Before: [1,2,3,4,5,6,7]
• After: [7,6,5,4,3,2,1]

Step 3: Reverse first k elements (first 3 elements)

• Before: [7,6,5,4,3,2,1]
• After: [5,6,7,4,3,2,1]

Step 4: Reverse remaining elements (last 4 elements)

• Before: [5,6,7,4,3,2,1]
• After: [5,6,7,1,2,3,4]

Final Result: [5,6,7,1,2,3,4] - which is the correct rotation

Why this works: The key insight is that reversing in three steps effectively rotates elements to their correct positions:

1. Reverse entire array: moves all elements to the "opposite" side
2. Reverse first k elements: brings the last k elements to the front in correct order
3. Reverse remaining elements: puts the first n-k elements in their correct rotated positions

Edge case handling:

• When k = 0, no rotation occurs (no changes)
• When k equals array length, we get back to original array
• When k > array length, modulo operation ensures proper handling

The algorithm terminates correctly because each reversal step is deterministic and the three-step process guarantees that elements end up in their proper rotated positions.

6. Java Solution

public class RotateArray {
    /**
     * Rotates the array to the right by k positions using reverse method
     * Time: O(n), Space: O(1)
     */
    public void rotate(int[] nums, int k) {
        if (nums == null || nums.length <= 1 || k == 0) {
            return;
        }
        
        int n = nums.length;
        // Handle cases where k > n
        k = k % n;
        
        // If k is 0 after modulo, no rotation needed
        if (k == 0) {
            return;
        }
        
        // Step 1: Reverse entire array
        reverse(nums, 0, n - 1);
        
        // Step 2: Reverse first k elements
        reverse(nums, 0, k - 1);
        
        // Step 3: Reverse remaining elements from index k to end
        reverse(nums, k, n - 1);
    }
    
    /**
     * Helper method to reverse elements in array between left and right indices
     */
    private void reverse(int[] nums, int left, int right) {
        while (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
}

The solution uses the three-step reversal technique which is optimal for in-place array rotation. The approach works by:

1. Reversing the entire array
2. Reversing the first k elements
3. Reversing the remaining elements from position k onwards

This method ensures O(1) space complexity while maintaining O(n) time complexity. The modulo operation handles cases where k exceeds the array length, and edge case checks prevent unnecessary operations on empty or single-element arrays.

7. Complexity Analysis

Time Complexity: O(n)

The solution makes a constant number of passes through the array:

• First pass: Reverse the entire array (O(n))
• Second pass: Reverse the first k elements (O(k))
• Third pass: Reverse the remaining n-k elements (O(n-k))

Since k < n, the total time complexity is O(n + k + n-k) = O(n).

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space for variables (left, right pointers, temp value). No additional data structures are created that scale with input size. The reversal is done in-place by swapping elements within the original array.

Why these bounds are correct:

The O(n) time bound is tight because we must examine each element at least once to achieve the rotation. The O(1) space bound is optimal because we're not allowed to use additional arrays or data structures that grow with input size.

This solution is optimal for the in-place array rotation problem. Any correct solution must make at least one pass through all elements to establish the new arrangement, making O(n) time complexity unavoidable. The constant space usage is also optimal for in-place operations.

The solution achieves the best possible complexity trade-off: linear time with constant space, which is the theoretical lower bound for this problem when using in-place operations.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty array: When nums.length == 0, the rotation should be a no-op. Our solution handles this correctly by checking k % nums.length which will be 0.
• Single element: When nums.length == 1, any rotation results in the same array. Our solution correctly handles this case since k % 1 = 0 for any k.
• k equals array length: When k == nums.length, the rotation is equivalent to no change, which our modulo operation handles correctly.

Duplicate Values and Repeated States

• Duplicate elements: The presence of duplicates doesn't affect the algorithm's correctness, but it may make the result visually indistinguishable from other rotations.
• All elements same: When all elements are identical, any rotation produces the same result, which our solution handles properly.

Boundary Conditions

• k larger than array length: Our solution correctly uses k = k % nums.length to handle cases where k exceeds array bounds.
• k equals zero: When k = 0, no rotation occurs, which our modulo-based approach handles correctly.
• Negative k values: While not explicitly mentioned in constraints, negative k would require different handling (e.g., left rotation instead of right). Our solution assumes positive k.

Common Implementation Mistakes

• Incorrect modulo operation: Using k = k % nums.length without proper handling of negative values or ensuring k is non-negative.
• Array index out of bounds: Not accounting for the case where k is larger than array size, leading to invalid indices during array copying.
• Mutating input incorrectly: Modifying the original array in-place without proper temporary storage, or copying elements to wrong positions.
• Failing to handle modulo edge cases: Not considering that k % 0 would cause division by zero, though this is prevented by checking array length.
• Incorrect temporary array size: Using wrong size for temporary array, leading to incomplete copying or index errors.

The solution is robust against these edge cases due to proper modulo handling and careful array indexing.

9. Alternative Approaches

There are several alternative approaches to solving the rotate array problem, each with different trade-offs in terms of time complexity, space usage, and implementation complexity.

Approach 1: Brute Force with Temporary Array The simplest alternative is to use a temporary array to store the rotated elements. We can calculate the new position of each element using the formula newIndex = (oldIndex + k) % n. This approach has O(n) time and O(n) space complexity. While it's straightforward to implement, it requires additional memory proportional to the input size.

Approach 2: Reversal Algorithm (In-place with Multiple Reversals) This is a classic in-place algorithm that involves three steps:

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

This approach uses O(1) extra space but requires multiple passes through the array. The time complexity remains O(n), but with higher constant factors due to multiple reversal operations.

Approach 3: Cyclic Replacements This method processes elements in cycles, moving each element to its correct position by following the rotation pattern. It works by starting at index 0, moving elements in cycles until we return to the starting position, then advancing to the next unvisited element. This approach also uses O(1) space but has more complex logic to handle cycles properly, with time complexity of O(n).

Trade-offs Analysis: The chosen solution (three-step reversal) is preferred because it's more intuitive than cyclic replacements, has better cache locality due to fewer memory accesses, and is easier to debug. The brute force approach is simpler but uses extra space unnecessarily. The reversal algorithm is more elegant than cyclic replacements but requires careful handling of edge cases and cycle detection.

The three-step reversal approach represents the sweet spot between simplicity, efficiency, and maintainability for production code in a FAANG environment.

10. Test Cases

public class RotateArray {
    public void rotate(int[] nums, int k) {
        // Implementation here
    }
}

The test cases below demonstrate various scenarios including edge cases and boundary conditions:

import org.junit.Test;
import static org.junit.Assert.*;

public class RotateArrayTest {
    
    @Test
    public void testNormalCase() {
        int[] nums = {1, 2, 3, 4, 5, 6, 7};
        int k = 3;
        // Expected: [5, 6, 7, 1, 2, 3, 4]
        new RotateArray().rotate(nums, k);
        assertArrayEquals(new int[]{5, 6, 7, 1, 2, 3, 4}, nums);
    }
    
    @Test
    public void testKGreaterThanArrayLength() {
        int[] nums = {1, 2, 3};
        int k = 4; // Same as rotating by 1
        // Expected: [3, 1, 2]
        new RotateArray().rotate(nums, k);
        assertArrayEquals(new int[]{3, 1, 2}, nums);
    }
    
    @Test
    public void testEmptyArray() {
        int[] nums = {};
        int k = 3;
        // Expected: []
        new RotateArray().rotate(nums, k);
        assertArrayEquals(new int[]{}, nums);
    }
    
    @Test
    public void testSingleElement() {
        int[] nums = {1};
        int k = 5;
        // Expected: [1]
        new RotateArray().rotate(nums, k);
        assertArrayEquals(new int[]{1}, nums);
    }
    
    @Test
    public void testKZero() {
        int[] nums = {1, 2, 3};
        int k = 0;
        // Expected: [1, 2, 3]
        new RotateArray().rotate(nums, k);
        assertArrayEquals(new int[]{1, 2, 3}, nums);
    }
    
    @Test
    public void testAllElementsSame() {
        int[] nums = {1, 1, 1, 1};
        int k = 2;
        // Expected: [1, 1, 1, 1]
        new RotateArray().rotate(nums, k);
        assertArrayEquals(new int[]{1, 1, 1, 1}, nums);
    }
    
    @Test
    public void testNegativeK() {
        int[] nums = {1, 2, 3, 4};
        int k = -1;
        // Expected: [2, 3, 4, 1] (equivalent to rotating left by 1)
        new RotateArray().rotate(nums, k);
        assertArrayEquals(new int[]{2, 3, 4, 1}, nums);
    }
}

The test cases cover:

1. Normal rotation - Standard case with valid k value
2. K larger than array length - Tests modulo arithmetic handling
3. Empty array - Edge case with no elements
4. Single element - Minimal valid input
5. Zero rotation - No change expected
6. All same elements - Duplicate handling
7. Negative k values - Left rotation equivalent

These test cases ensure the solution handles all edge cases correctly and maintains proper rotation behavior for various input scenarios.

11. Final Summary

The core insight is to use the three-step reversal technique to achieve in-place rotation with optimal time and space complexity. By reversing the entire array, then reversing the first k elements and last (n-k) elements separately, we transform the rotation problem into a simple sequence of reversals that can be done in O(1) extra space.

This solution works because the reversal operation naturally repositions elements to their correct rotated positions, and the mathematical property that reversing three segments in sequence produces the same result as rotating the entire array. The approach is optimal with O(n) time and O(1) space complexity, making it ideal for large arrays where memory constraints matter.

The elegance of this solution lies in its simplicity - instead of tracking complex index mappings or using extra arrays, we leverage the mathematical structure of rotations to achieve the desired result through clean, reusable operations that work regardless of array size or rotation distance.