Compute the spiral ordering of an 2D array

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:

Compute the spiral ordering of an 2D array test assertions

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.