Table of Contents
Problem Statement
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 - 10 <= k <= 105
Solution
Using an Auxiliary Array (O(n) Extra Space)
In this approach, you create a temporary array to hold the rotated version of the array, then copy it back into the original array. While this solution uses O(n) extra space, it is simple and clear.
This solution runs in O(n) time but uses O(n) extra space.
Steps
- Create a new array of the same size.
- For each element, calculate its new index after rotation.
- Copy the rotated elements back into the original array.
func rotate(nums []int, k int) {
n := len(nums)
k = k % n
tmp := make([]int, n)
for i := 0; i < n; i++ {
tmp[(i + k) % n] = nums[i]
}
// Copy elements back into original array
copy(nums, tmp)
}Golang Code Rotate Array
func rotate(nums []int, k int) {
index := 0
counter := 0
length := len(nums)
tmp := nums[0]
if length == 1 || k==0 || length == k || k > (10*10*10*10*10) || length > (10*10*10*10*10) {
return
}
seen := map[int]bool{0:true}
for j:=0 ;counter < length ; j++{
n := index + k
if index+k >= length {
n = (index+k) % length
}
nums[n], tmp = tmp, nums[n]
index = n
if seen[n]{
index = n+1
seen[n+1]= true
tmp=nums[index]
}else{
seen[n]= true
}
counter++
}
}
Cyclic Replacements (O(1) Extra Space)
After restructuring above Code
This method moves elements one by one to their new positions in a cyclic manner. The idea is to track where each element should go and keep swapping them in place until all elements have been rotated.
This solution works in O(n) time and uses O(1) extra space.
Steps
- Start from the first element, move it to its new position after rotation.
- Continue this for each element, using a temporary variable to hold values as they are swapped.
func rotate(nums []int, k int) {
n := len(nums)
k = k % n
count := 0 // Number of elements moved
for start := 0; count < n; start++ {
current := start
prev := nums[start]
for {
next := (current + k) % n
nums[next], prev = prev, nums[next]
current = next
count++
if start == current {
break
}
}
}
}Optimised Golang Code for Rotate Array
func rotate(nums []int, k int) {
length := len(nums)
// Handle trivial cases
if length == 1 || k == 0 || k%length == 0 {
return
}
// Optimize k to avoid unnecessary full cycles
k = k % length
index := 0
counter := 0
tmp := nums[0]
seen := map[int]bool{0: true}
for counter < length {
n := (index + k) % length
nums[n], tmp = tmp, nums[n]
index = n
if seen[index] {
index++
tmp = nums[index]
seen[index] = true
} else {
seen[index] = true
}
counter++
}
}
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?
In-Place Reversal Algorithm (O(1) Extra Space)
This is an efficient way to solve the problem using the reversal technique. It achieves O(1) extra space and works in O(n) time.
Steps
- Reverse the entire array.
- Reverse the first
kelements. - Reverse the last
n-kelements.
func reverse(nums []int, start, end int) {
for start < end {
nums[start], nums[end] = nums[end], nums[start]
start++
end--
}
}
func rotate(nums []int, k int) {
n := len(nums)
k = k % n // Handle cases where k is larger than n
// Step 1: Reverse the entire array
reverse(nums, 0, n-1)
// Step 2: Reverse the first k elements
reverse(nums, 0, k-1)
// Step 3: Reverse the remaining n-k elements
reverse(nums, k, n-1)
}
Summary
- In-place reversal: O(n) time and O(1) space.
- Cyclic replacements: O(n) time and O(1) space.
- Auxiliary array: O(n) time and O(n) space.
The first two solutions meet the requirement of O(1) extra space, while the third uses more space but is simple to implement.
Visit https: https://codeandalgo.com for more such contents.
Leave a Reply