Published on

# Rotate Matrix

Authors

## Problem

Write a method to rotate an image by 90 degrees given an image represented by a NxN matrix, where each pixel in the image is 3 bytes (clockwise). Is it possible to do this in place?

For

_3a = [[1, 2, 3],_3 [4, 5, 6],_3 [7, 8, 9]]

the output should be

_4solution(a) =_4 [[7, 4, 1],_4 [8, 5, 2],_4 [9, 6, 3]]

## Solution

The easiest way to rotate the matrix by 90 degrees clockwise is to implement the rotation in layers. Perform a circular rotation on each layer, moving the top edge to the right edget, the right edge to the bottom edge, the bottom edge to the left edge, and the left edge to the top edge.

How to perform four-way edge swap? Using copy between edge will require $O(n)$ memory which actually unnecessary. To implement inplace rotation we only need 1 temporary and swapping by index instead of by values.

## Code

main.go
_26func solution(a [][]int) [][]int {_26 n:= len(a)_26 for layer:=0;layer <= n/2; layer++{_26 first, last:= layer, n-1-layer_26 for i:=first; i < last ; i++{_26 offset:= i-first_26_26 // save top_26 top:= a[first][i]_26 _26 // left -> top_26 a[first][i] = a[last - offset][first]_26 _26 // bottom -> left_26 a[last-offset][first] = a[last][last-offset]_26 _26 // right -> bottom_26 a[last][last-offset] = a[i][last]_26 _26 // top -> right_26 a[i][last] = top_26 }_26 }_26 _26 return a_26}

## Dry Run

_29Input:_29[[10,9,6,3,7], _29 [6,10,2,9,7], _29 [7,6,3,8,2], _29 [8,9,7,9,9], _29 [6,8,6,8,2]]_29_29Result Rotate Layer 0_29_296 8 7 6 10 _298 10 2 9 9 _296 6 3 8 6 _298 9 7 9 3 _292 9 2 7 7_29_29Result Rotate Layer 1_29_296 8 7 6 10 _298 9 6 10 9 _296 7 3 2 6 _298 9 8 9 3 _292 9 2 7 7_29_29Result Rotate Layer 2_296 8 7 6 10 _298 9 6 10 9 _296 7 3 2 6 _298 9 8 9 3 _292 9 2 7 7