Rotating a matrix

Solving LeetCode 48. Rotate Image,

Here is a tutorial that can help you for a tricky little problem from LeetCode, and the solution in Swift. Have fun!

Image for post
Image for post

Prerequisites:

  • Some programming experience

Difficulty: Easy | Normal | Challenging

The problem

We rotate the following matrix:

Image for post
Image for post

Which becomes the following:

Image for post
Image for post

Method 1: Simple rotation

Rotate the corners

The index of the corners can be derived from the size of the matrix. Here we describe the position as a coordinate, and then the derivation in Swift (where size = matrix.count).

top left = [0,0] = matrix[0][0]

top right = [0,3–1] = matrix[0][size — 1]

bottom right = [3–1, 3–1] = matrix[size-1][size-1]

bottom left = [3–1, 0] = matrix[size-1][0]

so we can rotate these values through the following — because we need to rotate this clockwise we will inevitably wipe one of the values we need. To avoid this, we store one of the values as a temporary value.

let temp = matrix[0][0]

// top left == bottom left

matrix[0][0] = matrix [rows — 1][0]

// bottom left == bottom right

matrix[rows — 1][0] = matrix[3–1][3–1]

// bottom right == top right

matrix[3–1][3–1] = matrix[0][3–1]

// top right == top left (which has now changed)

matrix[0][3–1] = temp

Rotate the corners, generalised

We might have a matrix of any size n*n.

Image for post
Image for post

We can see that there is now an outer, and an inner cube that needs to be rotated.

Image for post
Image for post
The inner cube that needs to be rotated

We will have two loops to complete the rotation here (matrix.count / 2).

The first loop will be 0, and the first 1.

This means the top left hand corner of the outer loop will be matrix[0][0], and the top left hand corner of the inner loop will be matrix[1][1]. This gives us the clue — we can use the cycle to identify any corner in the matrix.

let temp = matrix[cycle][cycle]

let rows = matrix.count

// top left == bottom left

matrix[cycle][cycle] = matrix [rows — 1-cycle][cycle]

// bottom left == bottom right

matrix[rows — 1][cycle] = matrix[rows–1-cycle][rows–1-cycle]

// bottom right == top right

matrix[rows–1-cycle][rows–1-cycle] = matrix[cycle][rows–1-cycle]

// top right == top left (which has now changed)

matrix[cycle][rows–1] = temp

This now also works for the inner cube (the second cycle, named 1 here).

We can now process the corners — but what about the sides?

Rotate the middle

The middle of the ring will be rotated by moving to the appropriate place on the right of the square. We can rotate the two left ones

let rows = matrix.count

let cycle = 0

matrix[cycle][cycle + 1] = matrix[cycle + 2][cycle]

matrix[cycle][cycle + 2] = matrix[cycle + 1][cycle]

so matrix[cycle][cycle + …up to number of middle elements] = matrix [cycle + …up to number of middle elements][cycle]

For any matrix there will be a number of cycles

Even matricies = n / 2 cycles

Odd matrices = n / 2 cycles + 1 (as the inner cycle would be a single integer)

Outer loop — the number of cycles is 0.

Inner loop — the number of cycles is 1.

Method 2 : Rotate with Swaps

There is a possibility to just swap certain elements in the cube:

Image for post
Image for post
To finish off we would need to swap each row

For efficiency we swap the rows as we go:

For each row in the matrix, swap the location of the square with it’s reverse (if it exists).

Then reverse the matrix row, which gives the correctly ordered row.

Conclusion

This is a tricky problem, but certainly can be solved with some time spent thinking it through and getting to the core of the problem. Equally practicing arrays can really help us out when we are tackling a tricky problem like this!

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store