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:
- A "brute force" approach using .pop() and .unshift() array methods.
- 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:
- Once to reverse the entire array.
- Once to reverse from nums[0] to k.
- 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! :)
Top comments (7)
Why not just this?
Or, to avoid
arr
concatenation if it can be large,One thing I wonder about space complexity.
You have this
which is transpiled to
which is allocating space for a 2 items array N times (worst case). Surely, the browser engine would optimise the code but it would be better to create a helper array and reuse. Also, since the helper function is also an object, should we consider that as memory allocation?
Another alternative is not to rotate the array, but to rotate the indices used to access the array.
Nice one π