Rotate matrix
Given a 2d array, rotate it by 90 degrees
Example
1 2 3 4 13 9 5 1
5 6 7 8 => 14 10 6 2
9 10 11 12 15 11 7 3
13 14 15 16 16 2 8 4
Solution
- Start from the boundaries, 1,4,16,13 in the above example
- Do a four way swap (in clock wise direction)
- Move to the next elements (in clockwise direction)
- Repeat this until all elements have been swapped
- Shrink the matrix to the next inner layer and repeat
Code
def rotate_matrix(arr)
row_start = 0
col_start = 0
row_end = arr.size
col_end = arr.size
while row_start < row_end && col_start < col_end
# Setup the boundary points
r1 = row_start
c1 = col_start
r2 = row_end-1
c2 = col_start
r3 = row_end - 1
c3 = col_end -1
r4 = row_end - 1
c4 = col_start
(0...arr.size).times do
# Four way swap
temp = arr[r1][c1]
arr[r1][c1] = arr[r2][c2]
arr[r2][c2] = arr[r3][c3]
arr[r3][c3] = arr[r4][c4]
arr[r4][c4] = temp
c1 += 1
r2 += 1
c3 -= 1
r4 -= 1
end
# Shrink the boundaries of the matrix
row_start +=1
col_start +=1
row_end -= 1
col_end -= 1
end
end
Time complexity
- O(m x n) where m is the number of rows and n is the number of columns in the matrix