Rotate a 2D array (function)

Problem statement

Write a function that takes as input an n x n 2-dimensional array, and return the original array rotated 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 takes a 2-dimensional array and returns the original array rotated by 90 degrees clockwise:

/// Rotates the given matrix by 90 degrees clockwise. 
func rotate(m: Matrix) -> Matrix {
    // Prepare a constant & make a copy of the original matrix 
    let n = m.count; var om = m
    // Enumerate matrix in layers, working towards the center
    for layer in 0..<(n / 2) {
        // Compute layer's start and end
        let start = layer, end = n - 1 - layer
        // Touch and swap each item of the current layer
        for head in start..<end {
            // Calculate offset from the start
            let offset = head - start
            // Calculate Last eleMent's Column and Row
            let lmc = head, lmr = start,
            // Calculate First eleMent's Column and Row
                fmc = lmr,  fmr = end - offset,
            // Calculate Second eleMent's Column and Row
                smc = fmr, smr = end,
            // Calculate Third eleMent's Column and Row
                tmc = smr, tmr = lmc

            // Make a copy of the Last eleMent
            let lm = om[lmr][lmc]

            // Swap elements, first takes place of the last
            om[lmr][lmc] = om[fmr][fmc]
            // Swap elements, second takes place of the first
            om[fmr][fmc] = om[smr][smc]
            // Swap elements, third takes place of the second
            om[smr][smc] = om[tmr][tmc]
            // Swap elements, last takes place of the third
            om[tmr][tmc] = lm
        }
    }
    // Here is our matrix rotated by 90 degrees clockwise
    return om
}

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:

Rotate a 2D array (function) test assertions

Bits & pieces

This coding challenge is not very difficult to solve, still there are a few parts requiring extra effort - figure out how to enumerate matrix in layers and calculate coordinates of each element for the given iteration.

Lets get started!

First of all, we declare a constant with the number of edge’s elements for the given matrix and a local copy of the original matrix used to apply desired transformations:

// Prepare a constant & make a copy of the original matrix 
let n = m.count; var om = m

Next statement is the main loop to iterate over all layers in the matrix where n / 2 yields number of layers in the original matrix:

// Enumerate matrix in layers, working towards the center
for layer in 0..<(n / 2) {
  ... inner block of code ...
} 

Following statement, the first in the main loop computes start and end coordinates of the current layer to be processed since these values would be needed later to calculate coordinates of the elements being exchanged:

// Compute layer's start and end
let start = layer, end = n - 1 - layer

This statement is an inner loop used to process each and every item of the current layer defined by range between start and end variables:

// Touch and swap each item of the current layer
for head in start..<end {
  ... inner block of code ...
}

Next statement calculates an offset, that is the difference between current head and start positions:

// Calculate offset from the start
let offset = head - start

These statements below calculate row and column coordinates of the last, first, second and third elements accordingly. Note, however, some of the coordinates actually reuse already calculated values while others are result of simple calculations:

// Calculate Last eleMent's Column and Row
let lmc = head, lmr = start,
// Calculate First eleMent's Column and Row
    fmc = lmr,  fmr = end - offset,
// Calculate Second eleMent's Column and Row
    smc = fmr, smr = end,
// Calculate Third eleMent's Column and Row
    tmc = smr, tmr = lmc

This statment makes a copy of the last element’s value, so that we can safely perform transformation of the element in this position without losing the original data:

// Make a copy of the Last eleMent
let lm = om[lmr][lmc]

Next statements perform swap operation on values of the elements following the requirement, eq. rotate by 90 degrees clockwise:

// Swap elements, first takes place of the last
om[lmr][lmc] = om[fmr][fmc]
// Swap elements, second takes place of the first
om[fmr][fmc] = om[smr][smc]
// Swap elements, third takes place of the second
om[smr][smc] = om[tmr][tmc]
// Swap elements, last takes place of the third
om[tmr][tmc] = lm

Once the main loop is over, we are ready to return the rotated matrix to the calling code:

// Here is our matrix rotated by 90 degrees clockwise
return om

That’s all folks! 👀

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