Spiral Matrix: Another Matrix Layer Problem
In last week’s article, we learned how to rotate a 2D Matrix in place using Haskell’s mutable array mechanics. This taught us how to think about a Matrix in terms of layers, starting from the outside and moving in towards the center.
Today, we’ll study one more 2D Matrix problem that uses this layer-by-layer paradigm. For more practice dealing with multi-dimensional arrays, check out our Solve.hs course! In Module 2, you’ll study all kinds of different data structures in Haskell, including 2D Matrices (both mutable and immutable).
The Problem
Today’s problem is Spiral Matrix. In this problem, we receive a 2D Matrix, and we would like to return the elements of that matrix in a 1D list in “spiral order”. This ordering consists of starting from the top left and going right. When we hit the top right corner, we move down to the bottom. The we come back across the bottom row to the left, and then back up the top left. Then we continue this process on inner layers.
So, for example, let’s suppose we have this 4x4 matrix:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16This should return the following list:
[1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10]At first glance, it seems like a lot of our layer-by-layer mechanics from last week will work again. All the numbers in the “first” layer come first, followed by the “second” layer, and so on. The trick though is that for this problem, we have to handle non-square matrices. So we can also have this matrix:
1 2 3 4
5 6 7 8
9 10 11 12This should yield the list [1,2,3,4,8,12,11,10,9,5,6,7]. This isn’t a huge challenge, but we need a slightly different approach.
The Algorithm
We still want to generally move through the Matrix using a layer-by-layer approach. But instead of tracking the 4 corner points, we’ll just keep track of 4 “barriers”, imaginary lines dictating the “end” of each dimension (up/down/left/right) for us to scan. These barriers will be inclusive, meaning that they refer to the last valid row or column in that direction. We would call these “min row”, “min column”, “max row” and “max column”.
Now the general process for going through a layer will consist of 4 steps. Each step starts in a corner location and proceeds in one direction until the next corner is reached. Then, we can start again with the next layer.
The trick is the end condition. Because we can have rectangular matrices, the final layer can have a shape like 1 x n or n x 1, and this is a problem, because we wouldn’t need 4 steps. Even a square matrix of n x n with odd n would have a 1x1 as its final layer, and this is also a problem since it is unclear which “corner” this coordinate
Thus we have to handle these edge cases. However, they are easy to both detect and resolve. We know we are in such a case when “min row” and “max row” are equal, or if “min column” and “max column” are equal. Then to resolve the case, we just do one pass instead of 4, including both endpoints.
Rust Solution
For our Rust solution, let’s start by defining important terms, like we always do. For our terms, we’ll mainly be dealing with these 4 “barrier” values, the min and max for the current row and column. These are inclusive, so they are initially 0 and (length - 1). We also make a new vector to hold our result values.
pub fn spiral_order(matrix: Vec<Vec<i32>>) -> Vec<i32> {
let mut result: Vec<i32> = Vec::new();
let mut minR: usize = 0;
let mut maxR: usize = matrix.len() - 1;
let mut minC: usize = 0;
let mut maxC: usize = matrix[0].len() - 1;
...
}Now we want to write a while loop where each iteration processes a single layer. We’ll know we are out of layers if either “minimum” exceeds its corresponding “maximum”. Then we can start penciling in the different cases and phases of the loop. The edge cases occur when a minimum is exactly equal to its maximum. And for the normal case, we’ll do our 4-directional scanning.
pub fn spiral_order(matrix: Vec<Vec<i32>>) -> Vec<i32> {
let mut result: Vec<i32> = Vec::new();
let mut minR: usize = 0;
let mut maxR: usize = matrix.len() - 1;
let mut minC: usize = 0;
let mut maxC: usize = matrix[0].len() - 1;
while (minR <= maxR && minC <= maxC) {
// Edge cases: single row or single column layers
if (minR == maxR) {
...
break;
} else if (minC == maxC) {
...
break;
}
// Scan TL->TR
...
// Scan TR->BR
...
// Scan BR->BL
...
// Scan BL->TL
...
minR += 1;
minC += 1;
maxR -= 1;
maxC -= 1;
}
return result;
}Our “loop update” step comes at the end, when we increase both minimums, and decrease both maximums. This shows we are shrinking to the next layer.
Now we just have to fill in each case. All of these are scans through some portion of the matrix. The only trick is getting the ranges correct for each scan.
We’ll start with the edge cases. For a single row or column scan, we just need one loop. This loop should be inclusive across its dimension. Rust has a similar range syntax to Haskell, but it is less flexible. We can make a range inclusive by using = before the end element.
pub fn spiral_order(matrix: Vec<Vec<i32>>) -> Vec<i32> {
...
while (minR <= maxR && minC <= maxC) {
// Edge cases: single row or single column layers
if (minR == maxR) {
for i in minC..=maxC {
result.push(matrix[minR][i]);
}
break;
} else if (minC == maxC) {
for i in minR..=maxR {
result.push(matrix[i][minC]);
}
break;
}
...
}
return result;
}Now let’s fill in the other cases. Again, getting the right ranges is the most important factor. We also have to make sure we don’t mix up our dimensions or directions! We go right along minR, down along maxC, left along maxR, and then up along minC.
To represent a decreasing range, we have to make the corresponding incrementing range and then use .rev() to reverse it. This is a little inconvenient, giving up ranges that don’t look as nice, like for i in ((minC+1)..=maxC).rev(), because we want the decrementing range to include maxC but exclude minC.
pub fn spiral_order(matrix: Vec<Vec<i32>>) -> Vec<i32> {
...
while (minR <= maxR && minC <= maxC) {
...
// Scan TL->TR
for i in minC..maxC {
result.push(matrix[minR][i]);
}
// Scan TR->BR
for i in minR..maxR {
result.push(matrix[i][maxC]);
}
// Scan BR->BL
for i in ((minC+1)..=maxC).rev() {
result.push(matrix[maxR][i]);
}
// Scan BL->TL
for i in ((minR+1)..=maxR).rev() {
result.push(matrix[i][minC]);
}
minR += 1;
minC += 1;
maxR -= 1;
maxC -= 1;
}
return result;
}But once these cases are filled in, we’re done! Here’s the full solution:
pub fn spiral_order(matrix: Vec<Vec<i32>>) -> Vec<i32> {
let mut result: Vec<i32> = Vec::new();
let mut minR: usize = 0;
let mut maxR: usize = matrix.len() - 1;
let mut minC: usize = 0;
let mut maxC: usize = matrix[0].len() - 1;
while (minR <= maxR && minC <= maxC) {
// Edge cases: single row or single column layers
if (minR == maxR) {
for i in minC..=maxC {
result.push(matrix[minR][i]);
}
break;
} else if (minC == maxC) {
for i in minR..=maxR {
result.push(matrix[i][minC]);
}
break;
}
// Scan TL->TR
for i in minC..maxC {
result.push(matrix[minR][i]);
}
// Scan TR->BR
for i in minR..maxR {
result.push(matrix[i][maxC]);
}
// Scan BR->BL
for i in ((minC+1)..=maxC).rev() {
result.push(matrix[maxR][i]);
}
// Scan BL->TL
for i in ((minR+1)..=maxR).rev() {
result.push(matrix[i][minC]);
}
minR += 1;
minC += 1;
maxR -= 1;
maxC -= 1;
}
return result;
}Haskell Solution
Now let’s write our Haskell solution. We don’t need any fancy mutation tricks here. Our function will just take a 2D array, and return a list of numbers.
spiralMatrix :: A.Array (Int, Int) Int -> [Int]
spiralMatrix = ...
where
((minR', minC'), (maxR', maxC')) = A.bounds arrSince we used a while loop in our Rust solution, it makes sense that we’ll want to use a raw recursive function that we’ll just call f. Our loop state was the 4 “barrier” values in each dimensions. We’ll also use an accumulator value for our result. Since our barriers are inclusive, we can simply use the bounds of our array for the initial values.
spiralMatrix :: A.Array (Int, Int) Int -> [Int]
spiralMatrix = f minR' minC' maxR' maxC' []
where
((minR', minC'), (maxR', maxC')) = A.bounds arr
f :: Int -> Int -> Int -> Int -> [Int] -> [Int]
f = undefinedThis recursive function has 3 base cases. First, we have the “loop condition” we used in our Rust solution. If a min dimension value exceeds the max, we are done, and should return our accumulated result list.
Then the other two cases are our edge cases or having a single row or a single column for our final layer. In all these cases, we want to reverse the accumulated list. This means that when we put together our ranges, we want to be careful that they are in reverse order! So the edge cases should start at their max value and decrease to the min value (inclusive).
spiralMatrix :: A.Array (Int, Int) Int -> [Int]
spiralMatrix arr = f minR' minC' maxR' maxC' []
where
((minR', minC'), (maxR', maxC')) = A.bounds arr
f :: Int -> Int -> Int -> Int -> [Int] -> [Int]
f minR minC maxR maxC acc
| minR > maxR || minC > maxC = reverse acc
| minR == maxR = reverse $ [arr A.! (minR, c) | c <- [maxC,maxC - 1..minC]] <> acc
| minC == maxC = reverse $ [arr A.! (r, minC) | r <- [maxR,maxR - 1..minR]] <> acc
| otherwise = ...Now to fill in the otherwise case, we can do our 4 steps: going right from the top left, then going down from the top right, going left from the bottom right, and going up from the bottom left.
Like the edge cases, we make list comprehensions with ranges to pull the new numbers out of our input matrix. And again, we have to make sure we accumulate them in reverse order. Then we append all of them to the existing accumulation.
spiralMatrix :: A.Array (Int, Int) Int -> [Int]
spiralMatrix arr = f minR' minC' maxR' maxC' []
where
((minR', minC'), (maxR', maxC')) = A.bounds arr
f :: Int -> Int -> Int -> Int -> [Int] -> [Int]
f minR minC maxR maxC acc
...
| otherwise =
let goRights = [arr A.! (minR, c) | c <- [maxC - 1, maxC - 2..minC]]
goDowns = [arr A.! (r, maxC) | r <- [maxR - 1, maxR - 2..minR]]
goLefts = [arr A.! (maxR, c) | c <- [minC + 1..maxC]]
goUps = [arr A.! (r, minC) | r <- [minR+1..maxR]]
acc' = goUps <> goLefts <> goDowns <> goRights <> acc
in f (minR + 1) (minC + 1) (maxR - 1) (maxC - 1) acc'We conclude by making our recursive call with the updated result list, and shifting the barriers to get to the next layer.
Here’s the full implementation:
spiralMatrix :: A.Array (Int, Int) Int -> [Int]
spiralMatrix arr = f minR' minC' maxR' maxC' []
where
((minR', minC'), (maxR', maxC')) = A.bounds arr
f :: Int -> Int -> Int -> Int -> [Int] -> [Int]
f minR minC maxR maxC acc
| minR > maxR || minC > maxC = reverse acc
| minR == maxR = reverse $ [arr A.! (minR, c) | c <- [maxC,maxC - 1..minC]] <> acc
| minC == maxC = reverse $ [arr A.! (r, minC) | r <- [maxR,maxR - 1..minR]] <> acc
| otherwise =
let goRights = [arr A.! (minR, c) | c <- [maxC - 1, maxC - 2..minC]]
goDowns = [arr A.! (r, maxC) | r <- [maxR - 1, maxR - 2..minR]]
goLefts = [arr A.! (maxR, c) | c <- [minC + 1..maxC]]
goUps = [arr A.! (r, minC) | r <- [minR+1..maxR]]
acc' = goUps <> goLefts <> goDowns <> goRights <> acc
in f (minR + 1) (minC + 1) (maxR - 1) (maxC - 1) acc'Conclusion
This is the last matrix-based problem we’ll study for now. Next time we’ll start considering some tree-based problems. If you sign up for our Solve.hs course, you’ll learn about both of these kinds of data structures in Module 2. You’ll implement a tree set from scratch, and you’ll get lots of practice working with these and many other structures. So enroll today!