Another Algorithm: Rotate Array with JavaScript

Having worked on several problems on LeetCode, I find it helpful to document and review my solutions through published posts. The most recent problem I worked involved a single array.

The exercise calls for the creation of an function that accepts two parameters: an array of integers, and the number of positions the array needs to be shifted to the right.

For example, given the array (nums) with a value of [1,2,3,4,5,6,7] and the shift value (k) of 3, the expected output would be the array [5,6,7,1,2,3,4].

First Idea - Extract and Copy

What came to mind at first was simply to extract the last k items from the array and copy them to the head of a new array, then copy the remaining items to the end of the new array.

This solution would be quick and easy, allowing the array to be shifted in one pass, and requiring the additional space of one array.

A Backwards Solution, No Additional Space

A more challenging goal is to shift the array in place, without the space for additional array being allocated. It took me several attempts to find a methodology that would work before I stumbled on the rather backwards solution.

It turns out that by reversing sections of the array, the desired result can be achieved without additional space. The process does require two passes.

Let's start with the example array needing to be shifted to the right 3 places.

[1,2,3,4,5,6,7]

Reversing it would yield a new array with the shifted items at the beginning:

[7,6,5,4,3,2,1]

Then, reverse the first 3 items only:

[5,6,7,4,3,2,1]

And finally reverse the remaining items only to return the desired array:

[5,6,7,1,2,3,4]

The Code

I begaN with the skeleton function provided by LeetCode:

var rotate = function(nums, k) {
}

Then, I needed a function to reverse the array.

    var reverseArray = function(start, end) {
        for (i = start; i < end - i + start; i++) {
            let temp = nums[i];
            nums[i] = nums[end - i + start];
            nums[end - i + start]= temp;
        }
    }

That reverse function needs to be called 3 times.

• Reverse the entire array: reverseArray(0,nums.length-1)
• Reverse the first k elements: reverseArray(0, k-1)
• reverse the rest: reverseArray(k,nums.length-1)

There's one edge case that needs to be handled. When the shift ingeger(k) is larger than the length of the array, you end up with undefined elements. To fix this, I simply applied the modulus operator.

k = k % nums.length

Put it all together for my complete solution:

var rotate = function(nums, k) {
    var reverseArray = function(start, end) {
        for (i = start; i < end - i + start; i++) {
            let temp = nums[i];
            nums[i] = nums[end - i + start];
            nums[end - i + start]= temp;
        }
    } 

    k = k % nums.length
    reverseArray(0, nums.length-1)
    reverseArray(0, k-1);
    reverseArray(k, nums.length-1);
    return nums 
};

When submitted, my solution performed better than almost 65% of other entries. That's pretty good, but there's still work to be done.

These simple exercises are proving to be worth their weight in expanding my problem solving skills and creativity. Hopefully, this helps you other developers as well.

Happy coding!