Back to Arrays & Hashing
Medium
Rotate Array
Given an integer array `nums`, rotate the array to the right by `k` steps, where `k` is non-negative.
Examples
Input:nums = [1,2,3,4,5,6,7], k = 3
Output:[5,6,7,1,2,3,4]
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]
Input:nums = [-1,-100,3,99], k = 2
Output:[3,99,-1,-100]
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]
Constraints
1 <= nums.length <= 10^5-2^31 <= nums[i] <= 2^31 - 10 <= k <= 10^5
Approach
Create a new array of the same size. For each element at index `i` in the original array, place it at index `(i + k) % n` in the new array. Then copy all elements from the new array back to the original array.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(n)
This approach requires O(n) auxiliary space to store the rotated array before copying it back.
Solution.java
class Solution { public void rotate(int[] nums, int k) { int n = nums.length; int[] a = new int[n]; for (int i = 0; i < n; i++) { a[(i + k) % n] = nums[i]; } for (int i = 0; i < n; i++) { nums[i] = a[i]; } }}