The Technical Interview Guide to Array Transformations

A JavaScript guide to array transformations for interview prep and daily coding

Array is a list-like object, which has methods to perform traversal and mutation operations. We have reviewed array APIs in another article. Today we are going to look at some popular interview questions for array transformations.

Rotate One-Dimension Array

Given an array, we can rotate each element by k steps. If the end of the array is reached, the element will rotate to the beginning of the array. Use [1, 2, 3, 4, 5 , 6, 7] as an example. Rotating the array by one step will result in [7, 1, 2, 3, 4, 5 , 6]. Rotating the array by two steps will result in [6, 7, 1, 2, 3, 4, 5 ]. Rotating the array by nine steps will result in [6, 7, 1, 2, 3, 4, 5 ]. It is equivalent to rotating the array by two (9 % 7) steps. When k is negative, it rotates to the front, i.e., rotating the array by -4 steps will result in [5, 6, 7, 1, 2, 3, 4]. It is equivalent to rotating the array by 3 (7 - 4) steps.

Here is the algorithm to rotate each element in an array by k steps:

The above algorithm is based on intuition. It has a few boundaries to be taken care of.

There is another way to accomplish it. The following is a number array of length seven:

The reversed array looks like this:

Assuming k has been reduced to be in the range of [0, nums.length -1], rotating the elements in the array k steps moves the last k elements to the front. It is equivalent to reversing the reversed array from 0 to k — 1 and from k to nums.length -1.

If k = 3, reversing [7, 6, 5] and [4, 3, 2, 1] achieves the same result as rotating [1, 2, 3, 4, 5 , 6, 7] by three steps:

Here is the algorithm to rotate each element in an array by reversing three arrays:

Isn’t that neater?

Both algorithms’ time complexity is O(n), and space complexity is O(1).

These are verifying tests for both algorithms:

Transpose Two-Dimension Array

Given a 2D array, we can transpose the array by flipping the elements along the main diagonal, i.e., transpose the point [i][j] to the point [j][i].

Here is the algorithm to transpose a 2D array:

The algorithm’s time complexity is O(m⋅n), and space complexity is O(1).

These are verifying tests:

Rotate Two-Dimension Array

Given a 2D array, we can rotate it clockwise by 90°.

If we are given the array below left, rotating it clockwise by 90° becomes the array below right.

We perform an in-place rotation, assuming the array is an n x n array. The following diagram shows the array indexes of four corners:

We need to rotate the element at [i][j] along with its associated elements:

Here is the algorithm to rotate every four-pair element (top, right, bottom, and left) in a 2D array:

There is a short cut to rotate 1D arrays. Is there a short cut to rotate 2D arrays? Yes, indeed.

We draw the main diagonal and transpose the array by flipping the elements along the main diagonal. This generates the below right-side array.

Observe the transposed array. The original rows become columns. It is almost the targeted array, except that it needs to reverse the rows (flipping along the middle Y-axis).

Here is the algorithm to rotate a 2D array by transposing along the main diagonal and reversing all rows:

Both algorithms’ time complexity is O(m⋅n), and space complexity is O(1).

These are verifying tests for both algorithms:

If the interview question asks us to rotate a 2D array counterclockwise by 90°, how can we approach the problem?

Step 1: Transpose the array along the main diagonal. This generates the below right-side array.

Step 2: Reverse the columns (flipping along the middle X-axis).

Traverse in Spiral Order

Spiral order of a 2D array is starting from the top-left corner and traversing all elements in clockwise order until reaching the middle of the array.

The following is an example of spiral order of a 3x3 array.

Here is the algorithm to traverse a 2D array in spiral order:

The algorithm’s time complexity is O(n²), and space complexity is O(1).

These are verifying tests:

Search Two-Dimension Array

An ascending 2D array is a number array whose element values increase from left to right and top to bottom. We are asked to write an algorithm to search a target value in the ascending array.

For example, there are three 2D ascending arrays (A, B, and C) in the below diagram. Try to search the target value, 6. A and B return true, and C returns false.

We can perceive it as a 1D array from the top-left corner to the bottom-right corner. Then the problem becomes a binary search question.

Here is the algorithm to search a target value in an ascending 2D array:

The above is a binary search with some index conversions between one super-index and the 2D indexes.

The algorithm’s time complexity is O(log(m⋅n)), and space complexity is O(1).

It is also possible to check each row for whether the target is part of that row (less than or equals to the last element of the row). Here is the algorithm:

The algorithm’s time complexity is O(m⋅log n), and space complexity is O(1).

These are verifying tests for both algorithms:

Optimize Sparse Matrix Multiplication

Matrix multiplication is an operation that produces a matrix from two matrices. The number of columns in the first matrix must be equal to the number of rows in the second matrix. The resulting matrix has the number of rows of the first matrix and the number of columns of the second matrix. The following is an example for a 2x3 matrix times a 3x2 matrix to get a 2x2 matrix.

A sparse matrix is a matrix in which most of the elements are zero. There is no strict definition of how many elements need to be zero for a matrix to be considered sparse. Commonly the number of non-zero elements is roughly the number of rows or columns.

To get the result C = A x B, each element can be calculated as follows:

C[i][j] = A[i][k] * B[k][j] for every k.

If it is a sparse matrix, a lot of computation can be saved if A[i][k] is 0 or B[k][j] is 0.

Here is the algorithm to perform sparse matrix multiplication.

The algorithm’s time complexity is O(m⋅k⋅n), and space complexity is O(1).

The above algorithm can be modified to generate a non-zero data array from A. This saves time checking whether an element in A is zero. If B has a lot of columns, it could result in a performance gain.

Here is the algorithm to perform sparse matrix multiplication by generating a non-zero data array from A.

The algorithm’s time complexity is O(m⋅k⋅n), and space complexity is O(m⋅k).

These are verifying tests:

Optimize Matrix Chain Multiplication

Matrix multiplication is associative. For three matrices A, B, and C, (A x B) x C = A x (B x C):

However, the multiplication count is different:

The multiplication count for (A x B) x C is 10.
The multiplication count for A x (B x C) is 14.

When the chain is long, optimizing the multiplication order is essential for performance improvement.

We write an algorithm to find out the minimal multiplication count. Here we are given an array of matrix indexes, nums, which represent a chain of matrixes with dimensions of nums[0] x nums[1], nums[1] x nums[2], ..., nums[nums.length — 2] x nums[nums.length — 1]. Typically, dynamic programming is adopted here. dp[i][j] stands for the minimal multiplication count from the matrix[i] to matrix[j].

dp[i][j] = Math.max(dp[i][k] + dp[k + 1][j] + nums[i — 1] x nums[k] x nums[j]), for every i ≤ k < j.

Here is the algorithm to find out the minimal multiplication count with a given matrix chain indexes:

The algorithm’s time complexity is O(n²), and space complexity is O(n²).

These are verifying tests:

Conclusion

There are many variations of array transformation problems. Practice makes perfect.

The following are other interview guides:

Thanks for reading.

Want to Connect?

If you are interested, check out my directory of web development articles.