# Rotate a 2D array (data structure)

22 Sep 2018### 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).