The Technical Interview Guide to Array Transformations

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

Jennifer Fu
Oct 29 · 7 min read
large vine growing up and over a pergola with view of house behind
large vine growing up and over a pergola with view of house behind
Image credit: Author

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:

number array from 1 to 7
number array from 1 to 7

The reversed array looks like this:

number array from 7 to 1
number array from 7 to 1

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:

number array: 5, 6, 7, 1, 2, 3, 4
number array: 5, 6, 7, 1, 2, 3, 4

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

Isn’t that neater?

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].

2D number array transposed along diagonal axis
2D number array transposed along diagonal axis

Here is the algorithm to transpose a 2D array:

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.

2D number array rotated 90 degrees
2D number array rotated 90 degrees

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:

array indexes of four corners
array indexes of four corners

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

array indexes rotated
array indexes rotated

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.

array flipped along diagonal axis
array flipped along diagonal axis

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).

array flipped along vertical axis in middle row
array flipped along vertical axis in middle row

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

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.

array flipped along diagonal axis
array flipped along diagonal axis

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

array flipped along horizontal axis
array flipped along horizontal 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.

diagram showing a spiral path through an array
diagram showing a spiral path through an array

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

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 sorted 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.

Three 2D ascending arrays (A, B, and C)
Three 2D ascending arrays (A, B, and C)

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.

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:

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.

2x3 matrix times a 3x2 matrix to get a 2x2 matrix
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.

2x3 sparse matrix times a 3x2 sparse matrix to get a 2x2 sparse matrix
2x3 sparse matrix times a 3x2 sparse matrix to get a 2x2 sparse matrix

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 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.

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):

example of matrix multiplication
example of matrix multiplication

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:

These are verifying tests:

Conclusion

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

Thanks for reading. I hope this was helpful. You can see my other Medium publications here.

Better Programming

Advice for programmers.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store