Tricks to Traverse a 2D Array

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

However, framework thinking is not all-powerful. There are some specific techniques that are easy for those who know them, but difficult for those who do not. These can only be summarized and accumulated through frequent practice.

In this article, I will share some clever tricks for manipulating two-dimensional arrays. If you have a general impression of these, you won't be confused when you encounter similar problems in the future.

Clockwise/Counterclockwise Rotation of a Matrix

Rotating a two-dimensional array is a common problem in coding interviews, and LeetCode's 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 easy to understand: it asks you to rotate a two-dimensional matrix 90 degrees clockwise, with the challenge being to modify it "in place". The function signature is 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"

In 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 problem that you might want to try.

This little trick can be further utilized, for instance, in LeetCode Problem 61, "Rotate List": given a singly linked list, you are asked to rotate the list to the right by k places.

For example, given the singly linked list 1 -> 2 -> 3 -> 4 -> 5 and k = 2, your algorithm needs to return 4 -> 5 -> 1 -> 2 -> 3, i.e., move each node in the list to the right by 2 positions.

For this problem, don't foolishly move each node one by one. Let me clarify: it's about moving the last k nodes of the list to the front. Does that make sense now?

If not, here's another hint: moving the last k nodes to the head of the list is essentially reversing the first n - k nodes and the last k nodes in place, right?

Isn't this similar to the in-place word reversal discussed earlier? 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 details, such as k might be greater than the list length. You need to calculate the list length n first, then take k = k % n, ensuring k is not greater than the list length, and the final result is correct.

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

What is the purpose of discussing these two problems?

It aims to illustrate that sometimes our typical intuitive thinking may not be the most elegant from a computer's perspective; however, what the computer finds elegant might not be intuitive for us. This might be the charm of algorithms.