Rotate Array
Problem Description
Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.
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]
Constraints:
- 1 <= nums.length <= 105
- -231 <= nums[i] <= 231 - 1
- 0 <= k <= 105
Follow up:
- Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
- Could you do it in-place with
O(1)extra space?
Solve it on LeetCode
Approaches
1. Brute Force
Intuition:
The brute force approach involves rotating the array elements one step at a time. For each rotation, we move all the elements to their next position, simulating the rotation k times.
This matches the literal definition of “rotate right by k,” but it’s inefficient because elements are moved many times.
Steps:
Do this k times:
- Save the last element.
- Shift every element one step right.
- Put the saved element at the front.
Code:
- Time Complexity: O(n * k) - Performing
krotations, each requiring O(n) time. - Space Complexity: O(1) - No additional space used apart from input array.
2. Extra Array
Intuition:
By using an additional array, you can directly place each element in its rotated position. This avoids costly movement within the original array but requires additional space for storing the results.
Steps:
- Create a new array to hold rotated elements.
- Calculate and place each element in its final position.
- Copy the result back into the original array.
Code:
- Time Complexity: O(n) - Each element is processed a constant number of times.
- Space Complexity: O(n) - Additional array to hold rotated order.
3. Reverse the Array
Intuition:
The optimal solution utilizes array reversing. The underlying idea is that rotating an array is equivalent to reversing parts of the array.
Steps:
- Reverse the whole array.
- Reverse the first
kelements. - Reverse the remaining
n-kelements.
Code:
- Time Complexity: O(n) - Each reverse operation is O(n), and we perform a constant number of them.
- Space Complexity: O(1) - Reversal done in-place without extra space.
Example Walkthrough:
Input: nums = [1,2,3,4,5,6,7], k = 3
Step 1: Reverse the whole array.
Step 2: Reverse the first 3 elements.
Step 3: Reverse the remaining 4 (7 - 3) elements.