Sometimes the toughest questions we might be faced with in technical interviews as Software Engineers are the ones that seem simple at first glance.

Often writing a seemingly straightforward array or string algorithm will trip us up, due to us overcomplicating things or simply not knowing some of the more fundamental building blocks of working with those data types.

A question that embodies this perfectly is Rotating an Array.

The Prompt

Let's say you're given an array of numbers (nums), and an integer for how many times to the right that array should be "rotated" (k).

What does this mean? Let's visualize it:

nums = [1, 2, 3, 4, 5]

k = 3
=> [3, 4, 5, 1, 2]

k = 2
=> [4, 5, 1, 2, 3]

k = 1
=> [5, 1, 2, 3, 4]

As you can see, "rotating" an array is simply shifting those values to the right (or left) and putting them back on the opposite end of the array, sort of like rotating a carousel.

Now, how would be go about doing it?

The Solutions

What makes this question a compelling one in an interview setting is that there are multiple ways to solve it, all of which have different effects on runtime and space complexity. It's a good question to see the different ways a candidate goes about solving and explaining a "simple" problem since everyone might do it differently.

Today, we're going to look at two potential solutions:

1. A "brute force" approach using .pop() and .unshift() array methods.
2. A more complex solution using array reversals.

First we'll look at the code, and then break down what's happening in it.

1. Brute Force

const rotateArray1 = function(nums, k) {

  for (let i = 0; i < k; i++) {
      nums.unshift(nums.pop());
  }

  return nums;
}

This is considered the "brute force" approach, because it's essentially the most straightforward way that we're likely to think about the problem at first.

We know that we want to take something off of the end of the array and then put it on the front, and we know we want to do that (k) times, right?

This solution puts that exact direction into code. We run a for loop (k) times, on each pass pop()-ing off the last element of the array and giving it as an argument to unshift() it onto the front of the array. Then we return the array at the end.

The runtime complexity here is O(n * k), as each time we use unshift() JavaScript is re-seating each element in the array under the hood.

The space complexity is O(1), or constant space, since we're modifying the original array in-place. Great!

2. Reversal

const rotateArray2 = function(nums, k) {

  // reverse helper function
  function reverse(arr, start, end) {
    while (start < end) {
      [arr[start], arr[end]] = [arr[end], arr[start]];
      start++;
      end--;
    }
  }

  k %= nums.length;

  reverse(nums, 0, (nums.length - 1));
  reverse(nums, 0, (k - 1));
  reverse(nums, k, (nums.length - 1));

  return nums;
}

This is by far the most interesting solution of the three. This is the kind of algorithm solution you likely wouldn't think of initially, but might come to after thinking about the "bigger picture" for a while.

If you visualize the array being rotated, you'll notice a pattern:

nums = [1, 2, 3, 4, 5]

k = 2
=> [4, 5, 1, 2, 3]

// original array reversed
[5, 4, 3, 2, 1]

// reverse just the first (k) elements
[4, 5, 3, 2, 1]

// see where we're going?

// reverse from (k) to the end
[4, 5, 1, 2, 3]

And you've got the rotated result!

Again, this is a bit of a leap of logic that you might not initially think of, but works perfectly within the bounds we've been set for this problem.

As for our actual solution, what we're doing is establishing a helper function that takes in an array, a start index and an end index, and then uses ES6 syntax to swap the array[start] and array[end] elements before incrementing and decrementing the pointers.

Based off of our example above, we know we need to call this function three times:

1. Once to reverse the entire array.
2. Once to reverse from nums[0] to k.
3. Once to reverse from k to the end.

And we're done!

The runtime complexity here is O(n * 3), since we still need to reverse each element at least once, and we'll be doing that three times.

The space complexity here is, again, a constant O(1). Still great!

There you have it! Two completely different but equally viable solutions to the same problem. The advantage to knowing both is having more potential tools in your toolbox, and being able to answer a problem in different ways if an interviewer asks you to try a different approach.

I hope you've enjoyed reading! :)