# Compute the spiral ordering of an 2D array

21 Sep 2018### Problem statement

Write a program that takes an **N** x **N** matrix (*eq. 2D array*) as an argument and returns a **flat sequence** (*eq. single-dimensional array*) of elements from the original matrix in **spiral order**.

```
EXAMPLE:
Input: m = [[1,2,3],
[4,5,6],
[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]
```

### Solution

Here is the actual code of the algorithm that implements a solution to compute the spiral ordering of an 2D array:

```
/// Type alias to represent input of the algorithm.
typealias Matrix = [[Int]]
/// Type alias to represent output of the algorithm.
typealias Pieces = [Int]
/// Type alias to represent an intermediate state of the algorithm,
/// such as (x,y) coordinates and direction of a point in the matrix.
typealias Point = (x: Int, y: Int, dir: Int)
/// An integer constant to mark a visited point in the matrix.
let VISITED = 0
/// A Pieces value with elements of the original matrix in spiral order.
///
/// When you need to order elements of the specified matrix in spiral order, use `order` function.
///
/// - Parameter m: An instance of `N x N` matrix to order elements.
func order(m: Matrix) -> Pieces {
// Prepare state of the algorithm
var p: Point = (0,0,0), mm = m
// Prepare output collection of elements
var pcs = Pieces(repeating: 0, count: m.count * m.count)
// Process each & every element of the output collection
for i in 0...pcs.count - 1 {
// Copy value of the current point from the matrix
pcs[i] = mm[p.x][p.y]
// Mark current point as `visited` in the matrix
mm[p.x][p.y] = VISITED
// Compute next point + move this point to the next edge
let nx = next(p), rx = (p.x,p.y,p.dir + 1)
// Use the next point or use the point on the next edge
p = outside(nx, mm) ? next(rx) : nx
}
// Here is our answer
return pcs
}
```

Following is the traditional section with assertions to validate the code performs as advertised and establish a baseline for any improvement work in the future:

### Bits & pieces

This coding challenge might feel a bit troublesome at first, however a smart technique used to describe movement across `x`

/`y`

axes and coordinates validator both help a lot to write code that is easy to understand and reason about.

Lets get started!

The first statement initializes `p`

and `mm`

variables, `p`

is used to keep track of the current position the algorithm evaluates while `mm`

is used as a **read/write** copy of the original matrix:

```
// Prepare state of the algorithm
var p: Point = (0,0,0), mm = m
```

Next statement initializes `pcs`

variable, a single-dimensional array used as a storage to keep the final results:

```
// Prepare output collection of elements
var pcs = Pieces(repeating: 0, count: m.count * m.count)
```

Following code snippet, is the **main loop** to enumerate all elements in `pcs`

collection, one-by-one and copy corresponding values from the matrix:

```
// Process each & every element of the output collection
for i in 0...pcs.count - 1 {
... inner block of code ...
}
```

This statement simply copies a value of the current point in the matrix that the algorithm evaluates into the output collection of elements:

```
// Copy value of the current point from the matrix
pcs[i] = mm[p.x][p.y]
```

Next statement replaces value of the current point in the matrix with the sentinel value, therefore marking current element of the matrix as **visited**:

```
// Mark current point as `visited` in the matrix
mm[p.x][p.y] = VISITED
```

Following line of code, computes the subsequent point using `next`

helper function and also adjusts direction of the current point, for the case when coordinates of the next point in `nx`

variable are outside of the boundaries:

```
// Compute next point + move this point to the next edge
let nx = next(p), rx = (p.x,p.y,p.dir + 1)
```

Here is the code for `next`

helper function that implements an algorithm to calculate coordinates of the next point based on the current point coordinates and direction:

```
/// A Point value that is adjacent (eq. next) to the point specified as an argument.
///
/// When you need to compute the next point using coordinates
/// of the current point, use `next` function.
///
/// - Parameter p: An instance of the current point.
func next(_ p: Point) -> Point {
// Prepare initial state of the computation
let dx = [0,1,0,-1], dy = [1,0,-1,0], dir = p.dir % 4
// Calculate (x) and (y) coordinates of the next point
// in the same direction
return (p.x + dx[dir], p.y + dy[dir], p.dir)
}
```

Next statement, last in the **main loop**, verifies whether or not `nx`

point coordinates are outside of the matrix boundaries. If that’s the case, thanks to `?`

operator, we fallback to use `rx`

point to stay within the boundaries and compute the next point on the adjacent edge:

```
// Use the next point or use the point on the next edge
p = outside(nx, mm) ? next(rx) : nx
```

Here is the code for `outside`

helper function that performs validation whether or not coordinates of the given point `p`

are valid within the matrix boundaries. While validation of `x`

and `y`

coordinates might seem obvious, there is one more constraint to evaluate and that is whether the element has been already visited or not:

```
/// A Boolean value indicating whether the point is outside of the matrix boundaries.
///
/// When you need to check whether a given point is outside of the boundaries, use the
/// `outside` function.
///
/// - Parameter p: An instance of the point to check.
/// - Parameter m: An instance of the matrix to check with.
func outside(_ p: Point, _ m: Matrix) -> Bool {
// Check whether `x` coordinate is outside of the boundaries
if p.x < 0 || p.x >= m.count { return true }
// Check whether `y` coordinate is outside of the boundaries
if p.y < 0 || p.y >= m.count { return true }
// Check whether the given point is visited already
if m[p.x][p.y] == VISITED { return true }
// Looks like this point is not ouside of the boundaries
return false
}
```

As soon as the main loop is over, the function is ready to return a collection of values from `m`

that are in the spiral ordering:

```
// Here is our answer
return pcs
```

That’s all folks! 🤗

Here is a Swift playground for this article at Github: Compute ordering of an 2D array.