Rotate Array

Array, Two Pointers

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]

Solutions

The problem is asking to rotate an array to the right by k steps. This means that each element in the array should be moved k positions to the right, and the elements that go beyond the end of the array should be moved to the start of the array.

Approach – Brute Force Technique

In the brute force approach, we rotate the array k times. In each rotation, we move each element to its next position and move the last element to the start of the array.

Steps

1. Define the function: The function Rotate is defined with two parameters, nums (an array of integers) and k (the number of steps to rotate).

2. Outer loop: The outer loop runs k times. Each iteration of this loop corresponds to a single step of rotation.

3. Store the last element: Before shifting the elements, the last element of the array is stored in the variable temp. This is because it will be overwritten during the shifting process and we need to place it at the start of the array.

4. Shift elements to the right: The inner loop runs from the end of the array to the start, shifting each element one position to the right. This is done by setting nums[j] to nums[j - 1].

5. Place the last element at the start: After all elements have been shifted, there is an empty spot at the start of the array (i.e., nums[0]). The last element that we stored in temp is placed here.

6. Repeat: The process is repeated k times to achieve the required rotation.

public class Solution
{
    public void Rotate(int[] nums, int k)
    {
        for (int i = 1; i <= k; i++)
        {
            int temp = nums[nums.Length - 1];
            for (int j = nums.Length - 1; j > 0; j--)
            {
                nums[j] = nums[j - 1];
            }
            if (nums.Length > 0)
            {
                nums[0] = temp;
            }
        }
    }
}

Complexity

• Time Complexity: O(n*k)

• Auxiliary Space: O(1)

Approach – Two Pointers Technique

In the optimized approach, we use the reverse operation to achieve the rotation. We first reverse the entire array, then reverse the first k elements, and finally reverse the remaining n - k elements.

Steps

1. Calculate the effective number of rotations: The number of rotations k is taken modulo the length of the array n. This is because rotating the array n times doesn't change the array, so we only need to consider the remainder of k divided by n.

2. Reverse the entire array: The Reverse function is called with parameters 0 and n - 1, which reverses the entire array.

3. Reverse the first part of the array: The Reverse function is called again with parameters 0 and k - 1, which reverses the first k elements of the array.

4. Reverse the second part of the array: The Reverse function is called one more time with parameters k and n - 1, which reverses the remaining n - k elements of the array.

The Reverse function is a helper function that reverses the elements in the nums array between the start and end indices. It does this by swapping the elements at the start and end indices, and then incrementing start and decrementing end until start is no longer less than end.

public class Solution
{
    public void Rotate(int[] nums, int k)
    {
        int n = nums.Length;
        k = k % n;
        Reverse(nums, 0, n - 1);
        Reverse(nums, 0, k - 1);
        Reverse(nums, k, n - 1);
    }

    public void Reverse(int[] nums, int start, int end)
    {
        while (start < end)
        {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }

}

Complexity

• Time Complexity: O(n)

• Auxiliary Space: O(1)