This problem asks us to rotate an array of integers by a given number of steps. While seemingly straightforward, finding the most optimized solution can be a captivating puzzle for most of us.

In this article, we will delve into several distinct approaches to tackling this problem. We will start by discussing a brute force approach, which provides a simple yet naive solution. From there, we will progress towards more optimized techniques that improve both time and space complexity. But before that, we will see the problem statement.

Problem Statement:

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

Stay tuned for the upcoming sections where we dive into different approaches to solve this problem.

Approach 1: Brute Force

The approach is to perform the rotation in a loop for the given number of steps, shifting each element one position to the right.

In this approach, we iterate through the array k times.
In each iteration, we shift each element one position to the right by replacing the current element with the element before it.
The last element is stored in a variable lastElement before the shifting process begins, and then assigned to the first position nums[0] at the end of each iteration.
This process effectively rotates the array k steps to the right.

// ES6 Arrow Function
const rotateArray = (nums, k) => {
    const n = nums.length;
    k = k % n;

    for(let i = 0; i < k; i++) {
        const last = nums[n - 1];
        for(let j = n - 1; j > 0; j--) {
            nums[j] = nums[j-1];
        }

        nums[0] = last;
    }

    return nums;
}

Time Complexity: O(K * N)

As we iterate through the array k times, and in each iteration, it shifts each element one position to the right. Here, N is the length of the array.

Space Complexity: O(1)

Since it performs the rotation in-place without utilizing any additional data structures, hence, the space complexity is constant.

Note: This approach is not considered optimized for solving the problem of rotating an array with larger lengths. Its purpose is to provide an initial perspective on how one can approach the problem.

Approach 2: Using Extra Space

Another approach involves using an additional array to store the rotated elements. We copy the last k elements of the original array to the beginning of the new array, followed by the remaining elements from the original array.

So we create a new array rotatedArray to store the rotated elements.
We copy the last k elements of the original array to the beginning of rotatedArray.
Then we copy the remaining elements from the original array.
Return the rotatedArray.

// ES6 Arrow Function
const rotateArray = (nums, k) => {
    const n = nums.length;
    k = k % n;

    const rotatedArray = [];

    for(let i = n - k; i < n; i++) {
        rotatedArray.push(nums[i]);
    }

    for(let i = 0; i < n - k; i++) {
        rotatedArray.push(nums[i]);
    }

    return rotatedArray;
}

Time Complexity: O(N)

The algorithm iterates through the input array once to copy the elements to the rotatedArray. Therefore, the time complexity is O(n), where N is the size of the array.

Space Complexity: O(N)

Here, a new array is created to store the rotated elements and the size of this array is equal to the size of the input array. Therefore, the space complexity is O(N) as it requires additional space proportional to the size of the input.

Approach 3: Reversing Array

This is an optimized approach to solve this problem. It involves reversing the entire array, followed by reversing the first k elements and the remaining n-k elements separately. This approach allows us to achieve the desired rotation in-place without using extra space.

We define a function that reverses an array using the start and end index provided in the arguments.
First, we reverse the entire input array.
Then, we reverse the first k elements in the reversed array.
Finally, we reverse the remaining n-k elements in the reversed array.

// ES6 Arrow Function
const reverseArray = (arr, start, end) => {
    while(start < end) {
        [arr[start], arr[end]] = [arr[end], arr[start]]; 
        start++;
        end--;
    }
}

const rotateArray = (nums, k) => {
    const n = nums.length;
    k = k % n;

    reverseArray(nums, 0, n-1);
    reverseArray(nums, 0, k-1);
    reverseArray(nums, k, n-1);

    return nums;
}

Time Complexity: O(N)

There are three reverse operations on subarrays in the given input array. We are reversing the array using the reverseArray function and the time complexity of this function is O(N). Therefore, the overall time complexity of the rotateArray function is linear.

Space Complexity: O(1)

Since the rotation is in-place without taking any extra space and we are returning the same array, the space complexity is constant.

Important:

Why K = k % n, where n is the length of the input array.

To handle cases where the value of k is greater than or equal to the size of the array n. Since rotating an array by its size or multiples of its size results in the same array, it is unnecessary to perform redundant rotations. The purpose of k = k % n is to ensure that k is within the range of valid rotations.

By taking the modulo (%) operation with n, we reduce k to the equivalent number of rotations that fall within the array's bounds. This step effectively brings k to a value between 0 and n-1, ensuring that it represents the correct number of rotations needed within the given array size.

For example, if the array has a length of 5 (n = 5) and k is 7, the modulo operation k = k % n will set k to 2. This means that rotating the array 7 steps is equivalent to rotating it 2 steps within the array's size. This adjustment helps in optimizing the solution and avoids unnecessary rotations.

Including k = k % n in the code ensures that the solutions work correctly for any value of k, even if it exceeds the array's size.

And there you have it guys! We’ve explored different approaches, optimized our solutions, and hopefully had some fun along the way. I hope this article has provided you with valuable insights and helped you better understand the different approaches to solving this problem. Happy coding!

Problem: Leetcode 189

Rotate Array