Tricks to Traverse a 2D Array

Some readers have mentioned that after reading many articles on this site and mastering the framework thinking, they can solve most problems that follow a certain pattern.

However, framework thinking is not a panacea. There are specific techniques that are easy for those who know them and difficult for those who don't. These can only be mastered through extensive problem-solving and accumulation.

In this article, I will share some clever operations on two-dimensional arrays. Once you have an impression of these techniques, you won't be confused when encountering similar problems in the future.

Clockwise/Counterclockwise Matrix Rotation

Rotating a two-dimensional array is a common question in written exams. LeetCode problem #48 "Rotate Image" is a classic example:

48. Rotate Image | LeetCode |

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]

Example 2:

Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

Constraints:

• n == matrix.length == matrix[i].length
• 1 <= n <= 20
• -1000 <= matrix[i][j] <= 1000

The problem is straightforward: you need to rotate a two-dimensional matrix 90 degrees clockwise. The challenge is to modify it "in place", with the function signature as follows:

void rotate(int[][] matrix)

void rotate(vector<vector<int>>& matrix)

def rotate(matrix: List[List[int]]) -> None:

func rotate(matrix [][]int) {}

var rotate = function(matrix) {}

How do you rotate a 2D matrix "in place"? At first glance, it seems very complex and might require a clever algorithm to rotate the matrix layer by layer:

However, for this problem, you can't take the usual approach. Before explaining the clever solution, let's warm up with another algorithm problem that Google has used before:

You have a string s containing several words and spaces. Write an algorithm to reverse the order of all words in place.

For example, given the string:

s = "hello world labuladong"

Your algorithm should reverse the order of words in the string in place:

s = "labuladong world hello"

The conventional way is to split the string s into words by spaces, then reverse the order of these words, and finally join them back into a sentence. However, this method uses additional space and is not an "in-place" reversal.

The correct approach is to first reverse the entire string s:

s = "gnodalubal dlrow olleh"

Then reverse each word individually:

s = "labuladong world hello"

This way, we achieve the goal of reversing the order of all words in place. LeetCode problem 151, "Reverse Words in a String," is a similar issue, and you can try it out.

The little trick mentioned above can be further wrapped up. For example, you can take a look at LeetCode problem 61, "Rotate List": given a singly linked list, you need to rotate the list by moving each node to the right by k positions.

For instance, if the input linked list is 1 -> 2 -> 3 -> 4 -> 5 and k = 2, your algorithm should return 4 -> 5 -> 1 -> 2 -> 3, which means moving each node 2 positions to the right.

For this problem, don't naively move the nodes one by one. Let me translate this for you: it's essentially about moving the last k nodes to the head of the list. Got it?

If you haven't figured it out yet, here's another hint: moving the last k nodes to the head is the same as reversing the first n - k nodes and the last k nodes in place, right?

So, isn't this the same principle as reversing words in a string in place? You just need to reverse the entire list first, then reverse the first n - k nodes and the last k nodes separately to get the result.

Of course, there are some minor details in this problem. For example, k might be greater than the length of the list. In that case, you need to find the length n of the list first, then take the modulus k = k % n. This way, k won't be greater than the length of the list, and the final result will still be correct.

If you have time, try solving this problem yourself. It's relatively simple, so I won't include the code here.

What's the purpose of discussing these two problems?

It aims to illustrate that sometimes our intuitive thinking might not be the most elegant solution in the eyes of a computer; however, what the computer considers the most elegant solution might not be intuitive to us. Perhaps this is the charm of algorithms.