Did you read last week’s article on static vs dynamic arrays? If not, catch up now! This week we’re continuing the arrays theme and discussing multidimensional arrays. This is another data structure that you absolutely have to know to succeed in technical interviews, which is why several of our array questions in Interview Practice feature them.
Multidimensional Array Basics
What makes a multidimensional array different from a plain old array? And just what is a multidimensional array, anyway?
Basically, a multidimensional array is also a random-access data structure, but in this case the data is accessed by more than one index.
Some languages like C# have built-in support for multidimensional arrays. But other languages support multiple indices by creating an “array of arrays”. A multidimensional array in which you need
N numbers to reference a particular piece of data is an
N-dimensional array. In other words,
N is the number of indices needed to locate a single element in the array.
How do you access elements in a multidimensional array? In the “array of arrays” model, the elements at
arr[i] are arrays themselves. And element
arr[i][j] is the
jth element in the array
arr[i]. These arrays can be dynamic or static.
The good: The item lookup by index for multidimensional arrays is
O(1), and it’s easy to iterate over every element stored in a multidimensional array. You can use multiple indices that make sense for the problem you’re solving (consider using rows and columns for a problem about a chess board, for example), which makes it easier for you to read and maintain your code.
The bad: It’s not easy or quick to rearrange the elements in a multidimensional array, and it requires a long time to change its size.
Meet the 2D Array
Technically, it’s possible to have a multidimensional array of any size. But for technical interviews, it’s most important for you to be familiar with 2D arrays. 2D arrays are often used to implement:
- Matrices, where `matrix[i][j]` represents the element at row `i` and column `j`;
- Game boards like chess or checkers boards, where `board[row][col]` represents the state of the board at the location `(row, col)`;
- Maps, in which the map is divided into cells to represent different locations.
Jagged vs Regular Arrays
As we mentioned earlier, different languages have different ways of representing this kind of array. When implementing a 2D array as an “array of arrays” (i.e.
arr[i] is itself an array), there is no technical reason why
len(array[i]) == len(array[j]). If the subarrays have different lengths, we call this a jagged array.
But when we talk about multidimensional arrays, we often mean regular (or rectangular) arrays, in which each dimension has a fixed length.
TL;DR? Watch this video instead!
More of a visual learner? We get it. Watch this video to get up to speed on the basics of multidimensional arrays!
Up to speed on this handy data structure? Head on over to the arrays section of Interview Practice to solve some real multidimensional array-based technical interview questions!