I assume you know what a matrix is from your maths classes. They are two-dimensional containers of usually numeric values, but they can hold any type of data. They are widely used in various mathematical and other scientific fields such as machine learning.
Here’s an example of a 3×3 matrix
323446532438767
Matrices have columns and rows and their enumeration starts at 0. The coordinates of the various cells are given as row-column pairs. The top left hand cell is in row 0 and column 0, (0, 0) in short but there are other notations as well, I’ve even seen R0C0 at some point. So that’s the number 3 in the above example. Then 23 is in row 0, column 1 and so on. Here’s the coordinate table of a 4×4 matrix
0,00,10,20,31,01,11,21,32,02,12,22,33,03,13,23,3
In this post we’ll take a look at something simpler than machine learning though. Imagine that you’re tasked to build a circular matrix of integers. What do I mean by a circular matrix? The matrix starts with a certain integer in (0, 0), usually 0 or 1 and is then filled in an inward-spiraling pattern where the starting integer is incremented with every new cell. Here’s an example with a 4×4 spiraling matrix
12341213145111615610987
So we start with 1 then fill up the top row up to 4. Then we continue downwards to 7, followed by the bottom row and then back up again. We continue spiraling inwards until we reach the last cell at row 2, column 1 which has the value 16.
Matrices are relatively often used in technical interviews if the interviewer wants to see how comfortable you are with arrays. Matrices can be represented as 2-dimensional arrays which are not used that often in everyday programming and some candidates may feel uncomfortable using them.
The exact problem you are given can vary of course but building circular or spiraling matrices is one of the more complex ones in an interview. Knowing how to solve this particular matrix-related question will make you ready for other, similar types of question.
So how do we go about solving this? In questions where you need to work out some algorithm the key to success is often to find some kind of pattern in the data set. Can we see any patterns if we just look at the rows? Hmm, the top row is easy 1, 2, 3, 4 but the second row is 12, 13, 14, 5, that doesn’t reveal anything to me. Looking at the columns is even less promising 1, 12, 11, 10 and then 2, 13, 16, 9. Frankly, I don’t see anything that catches the eye, no symmetries, no patterns that can be modelled in a loop etc.
Therefore a more viable solution is to follow the index as it’s incremented and in the outer circle. We then do the same in the inner circle and continue inwards for any remaining circles.
So in the first iteration we want to fill the matrix as follows
In the second iteration we follow the same route with the remaining, smaller inner matrix
stop
This iteration will be an outer one in code. We’ll also need to iterate through the various sections
top row rightwardsright column downwardsbottom row leftwardsleft column upwards
We’ll write a function that accepts the dimension of the matrix. An incoming 4 means that we want to build a 4×4 matrix. Our implementation will return a list of integer lists where each list represents a row in the matrix. But wait, didn’t we say that matrices are best represented by a jagged array in code? Yes, we’ll use an array to build the matrix and then turn it into a list at the end of the function. This way you’ll be ready to build whichever data structure is required from you in the test. You’ll see why an array is better suited to hold the matrix data in just a bit.
Let’s start with some basic setup code
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Algorithms
{
public class MatrixBuilder
{
public List<List<int>> BuildMatrix(int n)
{
var result = new List<List<int>>();
var temporaryArray = new int[n][];
for (int i = 0; i < n; i++)
{
temporaryArray[i] = new int[n];
result.Add(new List<int>());
}
//main algorithm to be implemented here
for (int i = 0; i < temporaryArray.Length; i++)
{
result[i].AddRange(temporaryArray[i]);
}
return result;
}
}
}
We set up the return list and the temporary jagged array and fill them with some empty containers. We make sure that the array contents are copied to the list and return it from the function.
Here’s a short test suite
using Microsoft.VisualStudio.TestTools.UnitTesting;
using Algorithms;
using System;
using System.Collections.Generic;
using System.Text;
namespace Algorithms.Tests
{
[TestClass()]
public class MatrixBuilderTests
{
[TestMethod()]
public void BuildMatrixTests()
{
MatrixBuilder mb = new MatrixBuilder();
var matrix = mb.BuildMatrix(2);
CollectionAssert.AreEqual(new List<int>() { 1, 2 }, matrix[0]);
CollectionAssert.AreEqual(new List<int>() { 4, 3 }, matrix[1]);
matrix = mb.BuildMatrix(3);
CollectionAssert.AreEqual(new List<int>() { 1, 2, 3 }, matrix[0]);
CollectionAssert.AreEqual(new List<int>() { 8, 9, 4 }, matrix[1]);
CollectionAssert.AreEqual(new List<int>() { 7, 6, 5 }, matrix[2]);
matrix = mb.BuildMatrix(4);
CollectionAssert.AreEqual(new List<int>() { 1, 2, 3, 4 }, matrix[0]);
CollectionAssert.AreEqual(new List<int>() { 12, 13, 14, 5 }, matrix[1]);
CollectionAssert.AreEqual(new List<int>() { 11, 16, 15, 6 }, matrix[2]);
CollectionAssert.AreEqual(new List<int>() { 10, 9, 8, 7 }, matrix[3]);
}
}
}
We’ll need several counters. We need to know where we start and end each row and column in the main outer loop. Remember, the main outer loop serves to identify the dimensions of the array spirals
1111122112211111
In a 4×4 matrix we have 2 circles. They are denoted by purple 1’s and red 2’s in the above example. A 3×3 matrix will also have 2 circles but the inner circle has only one element, the one in the very middle of the matrix. A 2×2 matric has only a single circle.
The counter starts at 1 in row 0 and column 0, those are 3 variables that we can identify right there. Those are valid for the first circle. When we’re done with the first circle then the counter will have whatever value it has got up to in the iteration, whereas start row and start column will be 1. (1, 1) is the starting point for the inner circle of a 4×4 matrix – and for any other matrix of any size for that matter.
We also need to see how far out we’re allowed to go in each circular iteration. In the first iteration we’ll start at (0, 0) and the farthest we reach is at (3, 3), i.e. the bottom right hand cell of the matrix. In the second circle we start at (1, 1) and the max reach will be at (2, 2) otherwise we overwrite some of the values we have already calculated. It sounds like it’s not enough to know where we start, i.e. start column and start row, but where we end as well, i.e. the end column and end row.
If you refer back to the table with the arrows then we’ll need to set these row and column pointers as follows
start row 0end row n – 1, i.e. 3 in a 4×4 matrix to comply with the 0-based array indexingstart column 0end column n – 1, same as for end row
We start filling up the top row, i.e. from start row to end column, (0, 0) to (0, 3) in a 4×4 matrix. When we’re done then we increment the start row to 1. At this point we’re filling up the right hand column from (1, 3) to (3, 3). Then we decrement the end column and continue filling up the bottom row from (3, 2) to (3, 0). Finally we move up, i.e. decrement the end row and fill in the cells from (2, 0) to (1, 0). Recall that we incremented the start row to 1 so we don’t return to (0, 0) when filling up the left hand column.
At this point start row and start column are 1, end row and end column are 2, we’re ready for the inner circle where the same steps are taken.
So we’ll need the following
a main loop for each circle in the matrixinner loops for each section of the circletop rowright columnbottom rowleft column
Also, the bottom row and left column are iterated backwards, i.e. we need a for-loop where the iterator integer decreases to make sure we’re moving in the right direction.
We break the main outer loop when we have reached the end column and the end row, i.e. the start row and the start columns have converged to the end equivalents.
This is a lot of talking that’s difficult to visualise so let’s see a partial implementation with only the counter values and the various loops
using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.Remoting.Metadata.W3cXsd2001;
using System.Text;
using System.Threading.Tasks;
namespace Algorithms
{
public class MatrixBuilder
{
public List<List<int>> BuildMatrix(int n)
{
var result = new List<List<int>>();
var temporaryArray = new int[n][];
for (int i = 0; i < n; i++)
{
temporaryArray[i] = new int[n];
result.Add(new List<int>());
}
int counter = 1;
int startColumn = 0;
int endColumn = n - 1;
int startRow = 0;
int endRow = n - 1;
while (startColumn <= endColumn && startRow <= endRow)
{
//top row
for (int i = startColumn; i <= endColumn; i++)
{
}
//done with the row, increase the row pointer, i.e. move down in the matrix
startRow++;
//right column
for (int i = startRow; i <= endRow; i++)
{
}
//done with the column, move to the left
endColumn--;
for (int i = endColumn; i >= startColumn; i--)
{
}
//move up again on the right hand side of the matrix
endRow--;
for (int i = endRow; i >= startRow; i--)
{
}
//move to the right for the next loop
startColumn++;
}
for (int i = 0; i < temporaryArray.Length; i++)
{
result[i].AddRange(temporaryArray[i]);
}
return result;
}
}
}
Those loops pave the way for us to keep the index right, i.e. that we’re in the correct cell all the time. The while loop represents the circles in the matrix and is broken when the start and end indexes of the rows and columns have converged, i.e. we have reached the final cell in the matrix.
The 4 for-loops represent the 4 directions we’re taking, as outlined above. Also notice the decreasing direction of the second two loops that we also hinted at above.
Now that we have the correct pointers we can increase the counter variable within each for-loop, that’s simple
for (int i = startColumn; i <= endColumn; i++)
{
counter++;
}
startRow++;
for (int i = startRow; i <= endRow; i++)
{
counter++;
}
endColumn--;
for (int i = endColumn; i >= startColumn; i--)
{
counter++;
}
endRow--;
for (int i = endRow; i >= startRow; i--)
{
counter++;
}
startColumn++;
We have the pointers to the cell coordinates and the integer values we want to put in them. Now we need to use those to fill in the jagged array. This is where it’s absolutely necessary to use arrays and not lists because we fill the arrays the same way as we’re traversing the matrix. Each array within temporaryArray represents a row and when we’re done with the first for-loop we’ll have the following jagged array
1234xxxxxxxxxxxx
…where ‘x’ means “not yet properly filled in”.
The we move on and fill in the rightmost column
1234xxx5xxx6xxx7
So we need to access the last spots of arrays 2, 3, and 4 of the 2-dimensional array. We could not do the same with a list, there’s no equivalent accessor to a list where we can set the value at position n, we can only add new values to end of the list. So this is the main reason why it’s better to go for an array.
Next up we’ll fill up the bottom row
1234xxx5xxx610987
…and finally the left hand column
123412xx511xx610987
We then do the same in the “inner” matrix
12341213145111615610987
Now we need to select the correct indexes for the jagged array in the 4 for-loops.
In the first loop we move from left to right, i.e. from (0, 0) to (0, 3). So the row is constant, it will be equal to startRow. The column increases from 0 to endColumn. Hence we’ll use the following accessors
temporaryArray[startRow][i]
In the second for loop we move from (1, 3) to (3, 3). The column is equal to end column and row moves up from startRow to and including endRow. Recall the we incremented startRow by 1 after the first loop. Therefore we won’t accidentally overwrite cell (0, 3). Here’s the accessor in the second loop
temporaryArray[i][endColumn]
The in the third loop we move to the left from (3, 2) to (3, 0) and in the fourth loop upwards from (2, 0) to (1, 0).
Here’s the full solution
using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.Remoting.Metadata.W3cXsd2001;
using System.Text;
using System.Threading.Tasks;
namespace Algorithms
{
public class MatrixBuilder
{
public List<List<int>> BuildMatrix(int n)
{
var result = new List<List<int>>();
var temporaryArray = new int[n][];
for (int i = 0; i < n; i++)
{
temporaryArray[i] = new int[n];
result.Add(new List<int>());
}
int counter = 1;
int startColumn = 0;
int endColumn = n - 1;
int startRow = 0;
int endRow = n - 1;
while (startColumn <= endColumn && startRow <= endRow)
{
for (int i = startColumn; i <= endColumn; i++)
{
temporaryArray[startRow][i] = counter;
counter++;
}
startRow++;
for (int i = startRow; i <= endRow; i++)
{
temporaryArray[i][endColumn] = counter;
counter++;
}
endColumn--;
for (int i = endColumn; i >= startColumn; i--)
{
temporaryArray[endRow][i] = counter;
counter++;
}
endRow--;
for (int i = endRow; i >= startRow; i--)
{
temporaryArray[i][startColumn] = counter;
counter++;
}
startColumn++;
}
for (int i = 0; i < temporaryArray.Length; i++)
{
result[i].AddRange(temporaryArray[i]);
}
return result;
}
}
}
I think that was quite a challenging problem. Make sure you study it before your next job interview so that you can quickly present your solution and move on to the next problem.
+1 888-688-2939 
