Rotate a 2D array (data structure)

Problem statement

Write a data structure that takes as input an N x N matrix (eq. 2D array), and rotates the array by 90 degrees clockwise.

  EXAMPLE:

    Input:  [[ 1,  2,  3,  4],
             [ 5,  6,  7,  8],
             [ 9, 10, 11, 12],
             [13, 14, 15, 16]]

    Output: [13, 9, 5, 1, 14, 10, 6, 2, 15, 11, 7, 3, 16, 12, 8, 4]

Solution

Here is the actual code of the algorithm that implements a data structure to rotate the array by 90 degrees clockwise:

/// Wrapper type struct to provide clockwise-rotated access
/// to the elements of the original 2D array (eq. matrix).
struct RotatedMatrix<Element: Equatable>: Collection {

  /// Copy of the original matrix. 
  let matrix: [[Element]]

  /// Shorthand to the matrix's elements count.
  var size: Int { return matrix.count }

  /// The position of the first element in a nonempty collection.
  var startIndex: Int { return matrix.startIndex }

  /// The collection's "past the end" position---that is, the
  /// position one greater than the last valid subscript argument.
  var endIndex: Int { return size * size }

  /// Accesses the element at the specified position.
  subscript(position: Int) -> Element {
    // Guard access beyond boundaries of the original matrix
    precondition(position < endIndex, "Can't subscript an element ...")
    // Compute start and offset based on the current position 
    let start = size - 1, offset = position % size 
    // Translate position into coordinates of the matrix
    let x = start - offset, y = position / size
    // Query element from the original matrix
    return matrix[x][y]
  }

  /// Returns the position immediately after the given index.
  func index(after i: Int) -> Int {
    // Guard access beyond boundaries of the original matrix
    precondition(i < endIndex, "Can't advance beyond endIndex")
    // Advance to the next element
    return i + 1
  }
}

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:

Verify implementation of the data structure internals

Bits & pieces

This coding challenge is not very difficult to solve but might take some time to figure out how to access elements of the original matrix in the desired (eq. rotated) order using a simple translation technique.

Lets get started!

First of all, we declare our RotatedMatrix data structure and annotate the declaration with a generic constraint, such as <Element: Equatable> so that we can compare elements of the data structure in the context of test assertions. Also, we annotate data structure with Collection protocol that adds support to iterate over the data structure’s elements using for-in loop:

/// Wrapper type struct to provide clockwise-rotated access
/// to the elements of the original 2D array (eq. matrix).
struct RotatedMatrix<Element: Equatable>: Collection {
  ...
}

Next statement, declares a private field to store a local copy of the original matrix via the data structure’s default constructor:

/// Copy of the original matrix.
let matrix: [[Element]]

Following statement, declares a private computed property to access the count of the original matrix of a single dimension:

/// Shorthand to the matrix's elements count.
var size: Int { return matrix.count }

This statement, implements a computed property required by Collection protocol and simply delegates it the original matrix startIndex property:

/// The position of the first element in a nonempty collection.
var startIndex: Int { return matrix.startIndex }

Next snippet, implements another computed property required by Collection protocol and calculates the total number of elements in the original matrix:

/// The collection's "past the end" position---that is, the
/// position one greater than the last valid subscript argument.
var endIndex: Int { return size * size }

This function takes a position of an element from startIndex...endIndex, computes start (in reverse order) and offset within the matrix based on position. Finally, it translates these values into x and y coordinates of the element in the original matrix and returns its value:

/// Accesses the element at the specified position.
subscript(position: Int) -> Element {
  // Guard access beyond boundaries of the original matrix
  precondition(position < endIndex, "Can't subscript an element ...")
  // Compute start and offset based on the current position 
  let start = size - 1, offset = position % size 
  // Translate position into coordinates of the matrix
  let x = start - offset, y = position / size
  // Query element from the original matrix
  return matrix[x][y]
}

Last but not least, this function simply returns the position immediately after the given index and is one of the functions required to be implemented by Collection protocol:

/// Returns the position immediately after the given index.
func index(after i: Int) -> Int {
  // Guard access beyond boundaries of the original matrix
  precondition(i < endIndex, "Can't advance beyond endIndex")
  // Advance to the next element
  return i + 1
}

Finally, to enumerate elements of an N x N matrix using for .. in .. all you need to do is create an instance of RotatedMatrix and pass original matrix to the ctor:

// Here is the original matrix
let mx = [[1,2,3],[4,5,6],[7,8,9]]

// Enumerate elements of the matrix as if it was rotated
for x in RotatedMatrix(matrix: mx) { print(x) }

// Prints elements in rotated order: 7, 4, 1, 8, 5, 2, 9, 6, 3

That’s all folks! 🤖

Here is a Swift playground for this article at Github: Rotate a 2D array (data structure).