Rotate Array Solution for Accenture
Company: Accenture · Difficulty: Medium · Topics: Array, Two Pointers, Math
Problem Statement
Given an array, rotate the array to the right by k steps, where k is non-negative.
Key Understanding:
- Rotate the array to the right by k positions
- Elements that go beyond the end wrap around to the beginning
- k can be larger than the array length
- We need to handle the case where k > array length
Examples
Example 1:
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
- Rotate 1 steps to the right: [7,1,2,3,4,5,6]
- Rotate 2 steps to the right: [6,7,1,2,3,4,5]
- Rotate 3 steps to the right: [5,6,7,1,2,3,4]
Example 2:
Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation:
- Rotate 1 steps to the right: [99,-1,-100,3]
- Rotate 2 steps to the right: [3,99,-1,-100]
Example 3:
Input: nums = [1,2,3], k = 4
Output: [3,1,2]
Explanation:
- k = 4, but array length = 3
- Effective rotation = 4 % 3 = 1 step
- Rotate 1 step: [3,1,2]
Intuition
The key insight is that rotating an array by k steps is equivalent to:
1. Reversing the entire array
2. Reversing the first k elements
3. Reversing the remaining n-k elements
Mathematical Insight:
- If we rotate by k steps, the last k elements move to the front
- The first n-k elements move to the back
- We can achieve this using three reversals
Why Three Reversals Work:
- Original: [1,2,3,4,5,6,7], k = 3
- Reverse all: [7,6,5,4,3,2,1]
- Reverse first k: [5,6,7,4,3,2,1]
- Reverse rest: [5,6,7,1,2,3,4]
Approach
Approach 1: Using Extra Array (Simple)
Algorithm:
1. Create a new array of same size
2. Copy elements to new positions: newArr[(i + k) % n] = arr[i]
3. Copy back to original array
Approach 2: Juggling Algorithm
Algorithm:
1. Move elements in cycles
2. For each cycle, move elements by k positions
3. Continue until all elements are moved
Approach 3: Reversal Algorithm (Optimal)
Algorithm:
1. Reverse the entire array
2. Reverse the first k elements
3. Reverse the remaining n-k elements
Dry Run
Let's trace through Example 1: nums = [1,2,3,4,5,6,7], k = 3
Reversal Approach:
- Original: [1,2,3,4,5,6,7]
- Reverse all: [7,6,5,4,3,2,1]
- Reverse first 3: [5,6,7,4,3,2,1]
- Reverse rest: [5,6,7,1,2,3,4]
- Result: [5,6,7,1,2,3,4]
Extra Array Approach:
- k = 3, n = 7
- newArr[(0+3)%7] = newArr[3] = 1
- newArr[(1+3)%7] = newArr[4] = 2
- newArr[(2+3)%7] = newArr[5] = 3
- newArr[(3+3)%7] = newArr[6] = 4
- newArr[(4+3)%7] = newArr[0] = 5
- newArr[(5+3)%7] = newArr[1] = 6
- newArr[(6+3)%7] = newArr[2] = 7
- Result: [5,6,7,1,2,3,4]
Key Insights
1. Modulo Operation: k % n gives effective rotation
2. Three Reversals: Efficient in-place solution
3. Cyclic Nature: Elements wrap around the array
4. Edge Cases: Handle k > n and k = 0
Edge Cases
1. k = 0: No rotation needed
2. k = n: Array returns to original state
3. k > n: Use modulo to get effective rotation
4. n = 1: Single element array
5. k = 1: Simple one-step rotation
Solution
⚠️ Disclaimer: Don't jump directly to the solution, try it out yourself first. Only look at the solution after you've given it a good attempt.
Solution 1: Reversal Algorithm (Optimal)
Time Complexity: O(n) - Three passes through array
Space Complexity: O(1) - In-place solution
Solution 2: Extra Array
Time Complexity: O(n) - Two passes through array
Space Complexity: O(n) - Extra array needed
Solution 3: Juggling Algorithm
Time Complexity: O(n) - Single pass through array
Space Complexity: O(1) - In-place solution