189 Rotate Array

Description:

Given an integer array nums, rotate the elements to the right by k positions, where k is a non-negative integer.
Rotating to the right means that each element moves to an index that is k steps ahead, wrapping around to the beginning if necessary.

---

Example 1:

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

Example 2:

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

---

Constraints:

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

In-place rotation solution

The idea is to rotate the array in-place using reversals:

• Reverse the entire array.
• Reverse the first k elements.
• Reverse the rest of the array.

Why it works:

• Reversing the whole array puts the last k elements at the start (but in reverse order).
• Reversing each part restores the correct order.

Time Complexity: O(n)
Space Complexity: O(1)

class Solution {
    public void rotate(int[] nums, int k) {

        var step = nums.length % k;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, step - 1);
        reverse(nums, step, nums.length - 1);
    }

    public void reverse(int[] nums, int begin, int end) {
        while(begin < end) {
            var t = nums[begin];
            nums[begin] = nums[end];
            nums[end] = t;
            begin++;
            end--;
        }
    }
}

class Solution {
    fun rotate(nums: IntArray, k: Int): Unit {
        var n = nums.size

        var step = k % n

        reverse(nums, 0, n - 1)
        reverse(nums, 0, step - 1)
        reverse(nums, step, n - 1)
    }

    fun reverse(nums: IntArray, begin: Int, end: Int): Unit {
        var left = begin
        var right = end
        while(left < right) {
            var t = nums[left]
            nums[left] = nums[right]
            nums[right] = t
            left++
            right--
        }
    }
}

object Solution {
    def rotate(nums: Array[Int], k: Int): Unit = {
        var n = nums.length
        var step = k % n
        reverse(nums, 0, n - 1) 
        reverse(nums, 0, k - 1)
        reverse(nums, k, n - 1)
    }

    def reverse(nums: Array[Int], begin: Int, end: Int) : Unit = {
        var left = begin
        var right = end
        while(left < right) {
            var t = nums(left)
            nums(left) = nums(right)
            nums(right) = t
            left += 1
            right -= 1
        }
    }
}