Rotate Array - Java Solution

1. Introduction

This post explores a solution to the "Rotate Array" problem, a common task in array manipulation. The problem involves rotating an array to the right by a certain number of steps, and it is essential to achieve this efficiently.

Problem

Given an integer array nums, the task is to 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]

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

Output: [3,99,-1,-100]

2. Solution Steps

1. Normalize k to prevent unnecessary rotations (k %= nums.length).

2. Reverse the entire array.

3. Reverse the first k elements.

4. Reverse the remaining n-k elements.

5. This approach rearranges the elements to their correct rotated positions.

3. Code Program

public class RotateArray {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5, 6, 7};
        rotate(nums, 3);
        for (int num : nums) {
            System.out.print(num + " ");
        }
    }

    // Function to rotate the array to the right by k steps
    public static void rotate(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }

    // Helper method to reverse a portion of the array
    private static void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start++] = nums[end];
            nums[end--] = temp;
        }
    }
}

Output:

5 6 7 1 2 3 4

Explanation:

1. rotate: This function rotates nums to the right by k steps.

2. It first normalizes k to be within the array's bounds.

3. The function then reverses the entire array, followed by reversing the first k elements and then the rest.

4. This process effectively shifts the elements to their new positions after rotation.

5. The reverse helper function swaps elements in-place, ensuring O(1) extra space.

6. Overall, the method efficiently achieves array rotation with O(n) time complexity and O(1) space complexity.