189. Rotate Array #

Problem #

Given an array, rotate the array to the right by k steps, where k is non-negative.

Follow up:

Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
Could you do it in-place with O(1) extra space?

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 <= 2 * 10^4
-2^31 <= nums[i] <= 2^31 - 1
0 <= k <= 10^5

Problem Summary #

Given an array, move the elements in the array to the right by k positions, where k is non-negative.

Solution Ideas #

Solution 2: use an extra array. First move the element at index i in the original array to position (i+k) mod n, then copy the remaining elements back.
Solution 1: Since the problem requires not using extra space, the best solution for this problem is not Solution 2. In the final state after reversal, the last k mod n elements are moved to the beginning of the array, and the remaining elements are shifted right by k mod n positions to the end. Once the final state is determined, the transformation is straightforward. First reverse all elements in the array from beginning to end, so all elements at the tail move to the head. Then reverse the elements in the interval [0,(k mod n) − 1], and finally reverse the elements in the interval [k mod n, n − 1]; this satisfies the problem requirements.

Code #

package leetcode

// Solution 1 Time complexity O(n), space complexity O(1)
func rotate(nums []int, k int) {
	k %= len(nums)
	reverse(nums)
	reverse(nums[:k])
	reverse(nums[k:])
}

func reverse(a []int) {
	for i, n := 0, len(a); i < n/2; i++ {
		a[i], a[n-1-i] = a[n-1-i], a[i]
	}
}

// Solution 2 Time complexity O(n), space complexity O(n)
func rotate1(nums []int, k int) {
	newNums := make([]int, len(nums))
	for i, v := range nums {
		newNums[(i+k)%len(nums)] = v
	}
	copy(nums, newNums)
}