NUHMAN.com

Introduction

LeetCode 189 asks you to rotate an array to the right by k steps, where k is a non-negative integer. The problem involves shifting all elements in the array to the right by k positions, and elements that move past the last index should wrap around to the beginning of the array.

Problem Statement

Given an integer array nums and an integer k, you need to rotate the array nums such that each element is moved k positions to the right. You must do it in-place with O(1) extra space.

Function Signature:

go

func rotate(nums []int, k int)

Example 1:

go

nums := []int{1,2,3,4,5,6,7}
k := 3
rotate(nums, k)
fmt.Println(nums) // Output: [5,6,7,1,2,3,4]

Example 2:

go

nums := []int{-1,-100,3,99}
k := 2
rotate(nums, k)
fmt.Println(nums) // Output: [3,99,-1,-100]

Constraints:

• 1 <= nums.length <= 10^5
• -2^31 <= nums[i] <= 2^31 - 1
• 0 <= k <= 10^5

Approach

To solve this problem efficiently, we need to use an in-place approach, meaning we should avoid using extra space for a new array. The key insight for rotating the array is that:

1. Modulo Operation: If k is greater than the length of the array, rotating the array by k steps is equivalent to rotating it by k % n steps, where n is the length of the array. This is because after n rotations, the array will look exactly the same as it started.
2. Three-Step Reversal Approach:

• Reverse the entire array: First, reverse all elements in the array.
• Reverse the first k % n elements: Reverse the first k % n elements in the array.
• Reverse the remaining n - k % n elements: Reverse the remaining part of the array.

1. This three-step reversal method ensures that the elements are shifted in-place without needing extra space.

Time Complexity:

• O(n), where n is the number of elements in the array, since we only need to reverse portions of the array, which takes linear time.

Space Complexity:

• O(1), since we are using only a constant amount of extra space (no additional arrays are used).

Go Implementation

go

package main

import "fmt"

// Function to rotate the array in-place by k steps
func rotate(nums []int, k int) {
    n := len(nums)
    k = k % n // To handle cases where k > n

    // Reverse the entire array
    reverse(nums, 0, n-1)

    // Reverse the first k elements
    reverse(nums, 0, k-1)

    // Reverse the remaining n-k elements
    reverse(nums, k, n-1)
}

// Helper function to reverse a portion of the array
func reverse(nums []int, start int, end int) {
    for start < end {
        nums[start], nums[end] = nums[end], nums[start]
        start++
        end--
    }
}

func main() {
    // Test case 1
    nums1 := []int{1, 2, 3, 4, 5, 6, 7}
    k1 := 3
    rotate(nums1, k1)
    fmt.Println(nums1) // Output: [5, 6, 7, 1, 2, 3, 4]

    // Test case 2
    nums2 := []int{-1, -100, 3, 99}
    k2 := 2
    rotate(nums2, k2)
    fmt.Println(nums2) // Output: [3, 99, -1, -100]
}

Explanation of the Code:

1. rotate function:

• Input: The function takes the array nums and the integer k as inputs.
• Modulo Operation: We first reduce k by taking k % n, where n is the length of the array. This ensures that if k is larger than n, we only rotate the array by the necessary number of steps.
• Reversals: The array is then reversed in three steps:
• Reverse the entire array.
• Reverse the first k elements.
• Reverse the remaining n - k elements.
• In-place Rotation: All reversals are done in-place to meet the problem's requirement of O(1) extra space.

2. reverse function:

• Input: This helper function reverses the elements of the array between indices start and end.
• In-place Reversal: It swaps elements starting from start and end and keeps moving toward the center until start is less than end.

3. Main Function:

• The main function contains test cases where the function rotate is called with different arrays and values of k to check the correctness of the solution.

Example Walkthrough

Example 1:

Input: nums = [1, 2, 3, 4, 5, 6, 7], k = 3

1. Modulo Operation: k = k % n = 3 % 7 = 3, so we need to rotate the array by 3 positions.
2. Reverse Entire Array: nums = [7, 6, 5, 4, 3, 2, 1]
3. Reverse the first 3 elements: nums = [5, 6, 7, 4, 3, 2, 1]
4. Reverse the remaining 4 elements: nums = [5, 6, 7, 1, 2, 3, 4]
5. Final Output: [5, 6, 7, 1, 2, 3, 4]

Example 2:

Input: nums = [-1, -100, 3, 99], k = 2

1. Modulo Operation: k = k % n = 2 % 4 = 2, so we need to rotate the array by 2 positions.
2. Reverse Entire Array: nums = [99, 3, -100, -1]
3. Reverse the first 2 elements: nums = [3, 99, -100, -1]
4. Reverse the remaining 2 elements: nums = [3, 99, -1, -100]
5. Final Output: [3, 99, -1, -100]

Conclusion

LeetCode 189: Rotate Array can be solved efficiently using the three-step reversal approach. This approach rotates the array in-place with O(1) extra space and ensures that we get the correct result in O(n) time.