# 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: ### 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).