The Power of Basic Operations: Reverse as an Example

Example problem for this lesson: LeetCode 189 - Rotate Array (Easy)

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

Rotating an array is a very classic problem, and a typical one where you only have that “aha” moment after seeing the answer. When preparing for interviews, this is a must-know problem.

You may already know the solution to this problem, or you may have no idea. However, the focus of this article is not just explaining this problem. The answer itself is not what matters most — what matters is being able to analyze the underlying principles and apply them to other problems. This article will analyze how the solution derives from basic operations, and demonstrate the power of basic operations.

This article will cover:

• Multiple solutions to the example problem
• Various applications of the reverse operation
• What constitutes a basic operation
• Related problems and references

Solutions to the Rotate Array Problem

Below we’ll present three different solutions to the rotate array problem.

Solution 1: Using Extra Space

This is the most straightforward solution. We can use an auxiliary array to store the last k elements of the original array, then shift the remaining elements. The process of moving elements is shown below.

This solution has $O(n)$ time complexity and $O(k)$ space complexity. Obviously, it uses extra space and can be further optimized.

Solution 2: Cyclic Replacement

Some people’s first instinct is this approach. We can easily determine the final position each element should be in, so we can place them one by one into their correct positions. Taking $n=7$, $k=2$ as an example, the order of movement is: 1 ➝ 3 ➝ 5 ➝ 7 ➝ 2 ➝ 4 ➝ 6 ➝ 1. As shown in the figure below, all the arrows form a cycle.

Our replacement method works like this: first save element 1 in a temporary variable, place 6 into position 1, then place 4 into position 6… and so on, finally placing 1 into position 3.

However, the correctness of this solution is not easy to prove. In fact, when $n$ is a multiple of $k$, the replacement method described above doesn’t hold. As shown below, when $n=8$, $k=2$, there are actually two cycles:

• 1 ➝ 3 ➝ 5 ➝ 7 ➝ 1
• 2 ➝ 4 ➝ 6 ➝ 8 ➝ 2

If we start from 1, we can only replace elements 1, 3, 5, 7 — we’d need another pass starting from 2. As you can see, this approach is also quite cumbersome to implement. Although this method achieves $O(n)$ time complexity and $O(1)$ space complexity, it’s not recommended due to the complexity of its proof and implementation.

Solution 3: The Reverse Operation

You may already know the reverse-based solution. If not, this solution will give you that “aha” moment, much like the two-pointer solution for the Two Sum problem. First reverse the entire array, then reverse the two halves (the first k elements and the remaining elements) separately — and that achieves the rotation.

The process of the three reverse operations is shown below:

The corresponding code is as follows — very simple and clear. This solution is easy to understand, easy to prove, easy to remember, and achieves the optimal $O(n)$ time and $O(1)$ space. It can be considered the most elegant solution.

public void rotate(int[] nums, int k) {
    int N = nums.length;
    k %= N;
    reverse(nums, 0, N);
    reverse(nums, 0, k);
    reverse(nums, k, N);
}

void reverse(int[] nums, int begin, int end) {
    for (int i = begin, j = end - 1; i < j; i++, j--) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

The Power of Basic Operations

The three-reverse solution is indeed clever and effective, but how could you come up with it on your own? It seems there’s no better way than simply “having seen it before.” Of course, another way is to be thoroughly familiar with basic operations like reverse. For this problem, our goal is to achieve $O(n)$ time complexity and $O(1)$ space complexity. If we’re familiar with the reverse operation and know that it’s also an $O(n)$ time, $O(1)$ space operation, we can start thinking about whether reverse can get us there.

If I asked you to write code to reverse an array directly, anyone could easily write it and analyze its time and space complexity. But if we don’t treat array reversal as a basic operation, we can’t generalize it and apply it to other problems.

Psychologists have studied that human short-term memory capacity is roughly 7 units. In plain terms, the “workbench” we use when thinking about problems (or to use a metaphor, our “cache size”) is limited. If we treat reverse as a basic operation, then the rotate array problem only requires thinking about the combination of three operations. But if reverse has to be seen as a composition of multiple operations, our mental workbench can’t hold that many operations, and we likely won’t be able to figure out the answer.

The solution code above also follows the “basic operation” principle by writing reverse as a separate function, so the core code is just three lines. In fact, those familiar with C++ will know that C++ has a built-in array reversal operation std::reverse, and the solution written with it is remarkably concise:

void rotate(vector<int>& nums, int k) {
    k %= nums.size();
    reverse(nums.begin(), nums.end());
    reverse(nums.begin(), nums.begin() + k);
    reverse(nums.begin() + k, nums.end());
}

Indeed, while reverse might only be a conceptual basic operation in other languages, in C++ it’s already a language-level basic operation. This further illustrates how basic operations reduce the cognitive burden. Of course, I’m not advocating that C++ is superior — but exposure to different languages is genuinely beneficial. Sometimes it helps you break free from the limitations of your current language and prevents those limitations from becoming constraints on your thinking.

There are many other basic operations like reverse:

• Searching for a number in a sorted array takes $O(\log n)$ time (binary search)
• Partitioning an array around a pivot element into two halves takes $O(n)$ time (the partition step of quicksort)

Beyond these, the time and space complexities of heaps, balanced binary search trees, and hash tables that we’ve studied are all examples of basic operations. They’re not only helpful for analyzing algorithm complexity but also play a crucial role when we design algorithms.

More Applications of the Reverse Operation

The rotate array problem has an extended version — reversing words: LeetCode 151 - Reverse Words in a String (Medium)

Reverse the order of words in a string. For example:

• Input: “the sky is blue”
• Output: “blue is sky the”

If you just solved the rotate array problem, you should be able to easily figure out the approach for this one. The solution is essentially the same as rotating an array: first reverse the entire string, then reverse each individual word. The process is shown below.

Additionally, the reverse operation can be applied to string-to-number conversion problems. For example:

• LeetCode 415 - Add Strings (Easy)

Calculate the sum of two non-negative integers given as strings.

• LeetCode 504 - Base 7 (Easy)

Given an integer, convert it to base 7 and return it as a string.

Whether performing addition or base conversion, we compute the lower-order digits of the result first, then move to the higher-order digits. But since the output is in string form, this means constantly inserting characters at the beginning of the string, which has high time overhead.

One solution is to use an array or stack to temporarily store each digit of the result, then output it as a string at the end. Of course, there’s an even simpler approach: directly build a “reversed” result string, then reverse the string at the end.

Summary

Chapter 2.3 of Programming Pearls discusses the same rotate array problem. The title of this article, “The Power of Basic Operations,” comes directly from that chapter’s title. The book mentions a practical example: the “move lines” operation in a text editor is essentially an array rotation. The code implemented using the reverse operation worked correctly on the first try, while the linked-list-based code had several bugs. This is another advantage of basic operations not mentioned in this article: they’re easier to implement.

“Easy to come up with the solution” and “easy to write the implementation” are actually complementary. Because code is essentially the realization of ideas on paper. In interviews, we need to develop the ability to write correct, bug-free code within a limited time. So when practicing problems, what we need to focus on mastering isn’t the fastest or most flashy solutions, but rather the solutions with the clearest logic and the most concise code.

This article used reverse as an example to illustrate the important role of basic operations. I hope you’ll discover more basic operations as you practice. The next article is a companion piece that will introduce the role of “basic data structures” — stay tuned.