Given two integers M, N, and a 2D matrix Mat of dimensions MxN, clockwise rotate the elements in it.
Example 1:
Input:
M=3,N=3
Mat=[[1,2,3],[4,5,6],[7,8,9]]
Output:
4 1 2
7 5 3
8 9 6
Explanation:
Rotating the matrix clockwise gives this result.
Example 2:
Input:
M=2,N=3
Mat=[[1,2,3],[2,3,3]]
Output:
2 1 2
3 3 3
Explanation:
Rotating the matrix clockwise gives this result.
Your Task:
You don't need to read input or print anything. Your task is to complete the function rotateMatrix() which takes two integers M, N, and a 2D matrix as input parameters and returns the clockwise rotated matrix.
Expected Time Complexity:O(M*N)
Expected Auxillary Space:O(1)
Constraints:
1<=M,N,Mat[i][j]<=1000

Difficulty: EASY
Tags: Matrices

Data structures
Skill types: Data structures
Expected Time Complexity: O(M*N)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3

class Solution:
    def rotateMatrix(self, M, N, Mat):
        #code here

Solutions:
class Solution:

	def rotateMatrix(self, M, N, Mat):
		topLeft = (0, 0)
		while True:
			colLimit = N - topLeft[1]
			rowLimit = M - topLeft[0]
			if colLimit - 1 <= topLeft[1] or rowLimit - 1 <= topLeft[0]:
				break
			numToRotate = Mat[topLeft[0]][topLeft[1]]
			for i in range(topLeft[1] + 1, colLimit):
				(Mat[topLeft[0]][i], numToRotate) = (numToRotate, Mat[topLeft[0]][i])
			for i in range(topLeft[0] + 1, rowLimit):
				(Mat[i][colLimit - 1], numToRotate) = (numToRotate, Mat[i][colLimit - 1])
			for i in range(colLimit - 2, topLeft[1], -1):
				(Mat[rowLimit - 1][i], numToRotate) = (numToRotate, Mat[rowLimit - 1][i])
			for i in range(rowLimit - 1, topLeft[0], -1):
				(Mat[i][topLeft[0]], numToRotate) = (numToRotate, Mat[i][topLeft[0]])
			Mat[topLeft[0]][topLeft[1]] = numToRotate
			topLeft = (topLeft[0] + 1, topLeft[1] + 1)
		return Mat


class Solution:

	def rotateMatrix(self, m, n, mat):
		row = col = 0
		while row < m and col < n:
			if row + 1 == m or col + 1 == n:
				break
			prev = mat[row + 1][col]
			for i in range(col, n):
				(mat[row][i], prev) = (prev, mat[row][i])
			row += 1
			for j in range(row, m):
				(mat[j][n - 1], prev) = (prev, mat[j][n - 1])
			n -= 1
			if row < m:
				for i in range(n - 1, col - 1, -1):
					(mat[m - 1][i], prev) = (prev, mat[m - 1][i])
			m -= 1
			if col < n:
				for j in range(m - 1, row - 1, -1):
					(mat[j][col], prev) = (prev, mat[j][col])
			col += 1
		return mat


class Solution:

	def rotateMatrix(self, M, N, Mat):
		top = left = 0
		bottom = M - 1
		right = N - 1
		while top < bottom and left < right:
			starti = top
			startj = left
			temp = Mat[starti][startj]
			for i in range(left + 1, right + 1):
				(Mat[top][i], temp) = (temp, Mat[top][i])
			top += 1
			for i in range(top, bottom + 1):
				(Mat[i][right], temp) = (temp, Mat[i][right])
			right -= 1
			for i in range(right, left - 1, -1):
				(Mat[bottom][i], temp) = (temp, Mat[bottom][i])
			bottom -= 1
			for i in range(bottom, top - 1, -1):
				(Mat[i][left], temp) = (temp, Mat[i][left])
			left += 1
			Mat[starti][startj] = temp
		return Mat


class Solution:

	def rotateMatrix(self, M, N, Mat):
		if len(Mat) == 0:
			return [[]]
		top = 0
		bottom = M - 1
		left = 0
		right = N - 1
		while top < bottom and left < right:
			prev = Mat[top + 1][left]
			for i in range(left, right + 1):
				curr = Mat[top][i]
				Mat[top][i] = prev
				prev = curr
			top += 1
			for i in range(top, bottom + 1):
				curr = Mat[i][right]
				Mat[i][right] = prev
				prev = curr
			right -= 1
			for i in range(right, left - 1, -1):
				curr = Mat[bottom][i]
				Mat[bottom][i] = prev
				prev = curr
			bottom -= 1
			for i in range(bottom, top - 1, -1):
				curr = Mat[i][left]
				Mat[i][left] = prev
				prev = curr
			left += 1
		return Mat


class Solution:

	def rotateMatrix(self, M, N, Mat):

		def rotate(startc, startr, endc, endr):
			if startc >= endc or startr >= endr:
				return
			nxt = Mat[startr][startc]
			for c in range(startc + 1, endc + 1):
				(Mat[startr][c], nxt) = (nxt, Mat[startr][c])
			for r in range(startr + 1, endr + 1):
				(Mat[r][endc], nxt) = (nxt, Mat[r][endc])
			for c in range(endc - 1, startc - 1, -1):
				(Mat[endr][c], nxt) = (nxt, Mat[endr][c])
			for r in range(endr - 1, startr - 1, -1):
				(Mat[r][startc], nxt) = (nxt, Mat[r][startc])
			rotate(startc + 1, startr + 1, endc - 1, endr - 1)
		rotate(0, 0, N - 1, M - 1)
		return Mat


class Solution:

	def rotateMatrix(self, M, N, Mat):
		rows = 0
		cols = 0
		halfR = M // 2
		halfC = N // 2
		while rows < halfR and cols < halfC:
			prev01 = Mat[rows + 1][cols]
			prev02 = Mat[M - rows - 2][N - cols - 1]
			temp = M - rows - 1
			for i in range(cols, N - cols):
				(Mat[rows][i], prev01) = (prev01, Mat[rows][i])
				(Mat[temp][N - i - 1], prev02) = (prev02, Mat[temp][N - i - 1])
			temp = N - cols - 1
			for i in range(rows + 1, M - rows - 1):
				(Mat[i][temp], prev01) = (prev01, Mat[i][temp])
				(Mat[M - i - 1][cols], prev02) = (prev02, Mat[M - i - 1][cols])
			rows += 1
			cols += 1
		return Mat


class Solution:

	def swap(self, Mat, i, j, i2, j2):
		(Mat[i][j], Mat[i2][j2]) = (Mat[i2][j2], Mat[i][j])

	def rotateMatrix(self, M, N, Mat):
		t = l = 0
		r = N - 1
		b = M - 1
		while b - t + 1 >= 2 and r - l + 1 >= 2:
			for j in range(l + 1, r):
				self.swap(Mat, t, j, t, l)
			for i in range(t, b):
				self.swap(Mat, i, r, t, l)
			for j in range(r, l, -1):
				self.swap(Mat, b, j, t, l)
			for i in range(b, t, -1):
				self.swap(Mat, i, l, t, l)
			t += 1
			b -= 1
			l += 1
			r -= 1
		return Mat


class Solution:

	def rotateMatrix(self, M, N, Mat):
		(row, col) = (0, 0)
		(a, b) = (M, N)
		(prev, curr) = (0, 0)
		while row < M and col < N:
			if row + 1 == M or col + 1 == N:
				break
			prev = Mat[row + 1][col]
			for i in range(col, N):
				curr = Mat[row][i]
				Mat[row][i] = prev
				prev = curr
			row += 1
			for i in range(row, M):
				curr = Mat[i][N - 1]
				Mat[i][N - 1] = prev
				prev = curr
			N -= 1
			if row < M:
				for i in range(N - 1, col - 1, -1):
					curr = Mat[M - 1][i]
					Mat[M - 1][i] = prev
					prev = curr
			M -= 1
			if col < N:
				for i in range(M - 1, row - 1, -1):
					curr = Mat[i][col]
					Mat[i][col] = prev
					prev = curr
			col += 1
		return Mat


class Solution:

	def rotateMatrix(self, M, N, matrix):
		top = left = 0
		bottom = M - 1
		right = N - 1
		while left < right and top < bottom:
			prev = matrix[top + 1][left]
			for i in range(left, right + 1):
				curr = matrix[top][i]
				matrix[top][i] = prev
				prev = curr
			top += 1
			for i in range(top, bottom + 1):
				curr = matrix[i][right]
				matrix[i][right] = prev
				prev = curr
			right -= 1
			for i in range(right, left - 1, -1):
				curr = matrix[bottom][i]
				matrix[bottom][i] = prev
				prev = curr
			bottom -= 1
			for i in range(bottom, top - 1, -1):
				curr = matrix[i][left]
				matrix[i][left] = prev
				prev = curr
			left += 1
		return matrix


class Solution:

	def rotateMatrix(self, M, N, Mat):
		top = 0
		down = M - 1
		left = 0
		right = N - 1
		while top < down and left < right:
			prev = Mat[top + 1][left]
			for i in range(left, right + 1):
				curr = Mat[top][i]
				Mat[top][i] = prev
				prev = curr
			top += 1
			for i in range(top, down + 1):
				curr = Mat[i][right]
				Mat[i][right] = prev
				prev = curr
			right -= 1
			for i in range(right, left - 1, -1):
				curr = Mat[down][i]
				Mat[down][i] = prev
				prev = curr
			down -= 1
			for i in range(down, top - 1, -1):
				curr = Mat[i][left]
				Mat[i][left] = prev
				prev = curr
			left += 1
		return Mat


class Solution:

	def rotateMatrix(self, M, N, Mat):
		(row, col) = (0, 0)
		lastrow = M
		lastcol = N
		(prev, cur) = (0, 0)
		while row < lastrow and col < lastcol:
			if row + 1 == lastrow or col + 1 == lastcol:
				break
			prev = Mat[row + 1][col]
			for i in range(col, lastcol):
				cur = Mat[row][i]
				Mat[row][i] = prev
				prev = cur
			row += 1
			for i in range(row, lastrow):
				cur = Mat[i][lastcol - 1]
				Mat[i][lastcol - 1] = prev
				prev = cur
			lastcol -= 1
			if row < lastrow:
				for i in range(lastcol - 1, col - 1, -1):
					cur = Mat[lastrow - 1][i]
					Mat[lastrow - 1][i] = prev
					prev = cur
			lastrow -= 1
			if col < lastcol:
				for i in range(lastrow - 1, row - 1, -1):
					cur = Mat[i][col]
					Mat[i][col] = prev
					prev = cur
			col += 1
		return Mat


class Solution:

	def rotateMatrix(self, M, N, Mat):
		r = 0
		c = 0
		hR = M // 2
		hC = N // 2
		while r < hR and c < hC:
			prev01 = Mat[r + 1][c]
			prev02 = Mat[M - r - 2][N - c - 1]
			temp = M - r - 1
			for i in range(c, N - c):
				(Mat[r][i], prev01) = (prev01, Mat[r][i])
				(Mat[temp][N - i - 1], prev02) = (prev02, Mat[temp][N - i - 1])
			temp = N - c - 1
			for i in range(r + 1, M - r - 1):
				(Mat[i][temp], prev01) = (prev01, Mat[i][temp])
				(Mat[M - i - 1][c], prev02) = (prev02, Mat[M - i - 1][c])
			r += 1
			c += 1
		return Mat


class Solution:

	def rotateMatrix(self, m, n, mat):
		sr = 0
		sc = 0
		er = m - 1
		ec = n - 1
		while sr < er and sc < ec:
			prev = mat[sr + 1][sc]
			for i in range(sc, ec + 1):
				(prev, mat[sr][i]) = (mat[sr][i], prev)
			sr = sr + 1
			for i in range(sr, er + 1):
				(mat[i][ec], prev) = (prev, mat[i][ec])
			ec = ec - 1
			for i in range(ec, sc - 1, -1):
				(prev, mat[er][i]) = (mat[er][i], prev)
			er = er - 1
			for i in range(er, sr - 1, -1):
				(prev, mat[i][sc]) = (mat[i][sc], prev)
			sc = sc + 1
		return mat


class Solution:

	def rotateMatrix(self, M, N, Mat):
		l = 0
		r = len(Mat[0]) - 1
		t = 0
		b = len(Mat) - 1
		while t < b and l < r:
			prev = Mat[t + 1][l]
			for i in range(l, r + 1):
				curr = Mat[t][i]
				Mat[t][i] = prev
				prev = curr
			t = t + 1
			for i in range(t, b + 1):
				curr = Mat[i][r]
				Mat[i][r] = prev
				prev = curr
			r = r - 1
			for i in range(r, l - 1, -1):
				curr = Mat[b][i]
				Mat[b][i] = prev
				prev = curr
			b = b - 1
			for i in range(b, t - 1, -1):
				curr = Mat[i][l]
				Mat[i][l] = prev
				prev = curr
			l = l + 1
		return Mat


class Solution:

	def rotateMatrix(self, M, N, Mat):
		sr = 0
		er = M - 1
		sc = 0
		ec = N - 1
		while sr < er and sc < ec:
			prev = Mat[sr + 1][sc]
			for i in range(sc, ec + 1):
				curr = Mat[sr][i]
				Mat[sr][i] = prev
				prev = curr
			for i in range(sr + 1, er + 1):
				curr = Mat[i][ec]
				Mat[i][ec] = prev
				prev = curr
			for i in range(ec - 1, sc - 1, -1):
				curr = Mat[er][i]
				Mat[er][i] = prev
				prev = curr
			for i in range(er - 1, sr - 1, -1):
				curr = Mat[i][sc]
				Mat[i][sc] = prev
				prev = curr
			sr += 1
			sc += 1
			ec -= 1
			er -= 1
		return Mat


class Solution:

	def rotateMatrix(self, M, N, Mat):
		hm = M // 2
		hn = N // 2
		i = 0
		j = 0
		while i < hm and j < hn:
			temp = Mat[i][j]
			for tj in range(j + 1, N - j):
				t = Mat[i][tj]
				Mat[i][tj] = temp
				temp = t
			for ti in range(i + 1, M - i):
				t = Mat[ti][N - j - 1]
				Mat[ti][N - j - 1] = temp
				temp = t
			for tj in range(N - j - 2, j - 1, -1):
				t = Mat[M - i - 1][tj]
				Mat[M - i - 1][tj] = temp
				temp = t
			for ti in range(M - i - 2, i - 1, -1):
				t = Mat[ti][j]
				Mat[ti][j] = temp
				temp = t
			i += 1
			j += 1
		return Mat


class Solution:

	def rotateMatrix(self, M, N, Mat):
		r = 0
		c = 0
		while r < M and c < N:
			if r + 1 == M or c + 1 == N:
				break
			prev = Mat[r + 1][c]
			for i in range(c, N):
				(Mat[r][i], prev) = (prev, Mat[r][i])
			r += 1
			for j in range(r, M):
				(Mat[j][N - 1], prev) = (prev, Mat[j][N - 1])
			N -= 1
			if r < M:
				for i in range(N - 1, c - 1, -1):
					(Mat[M - 1][i], prev) = (prev, Mat[M - 1][i])
			M -= 1
			if c < N:
				for j in range(M - 1, r - 1, -1):
					(Mat[j][c], prev) = (prev, Mat[j][c])
			c += 1
		return Mat


class Solution:

	def rotateMatrix(self, M, N, Mat):
		rows = 0
		cols = 0
		R1 = M // 2
		C1 = N // 2
		while rows < R1 and cols < C1:
			prev1 = Mat[rows + 1][cols]
			prev2 = Mat[M - rows - 2][N - cols - 1]
			temp = M - rows - 1
			for i in range(cols, N - cols):
				(Mat[rows][i], prev1) = (prev1, Mat[rows][i])
				(Mat[temp][N - i - 1], prev2) = (prev2, Mat[temp][N - i - 1])
			temp = N - cols - 1
			for i in range(rows + 1, M - rows - 1):
				(Mat[i][temp], prev1) = (prev1, Mat[i][temp])
				(Mat[M - i - 1][cols], prev2) = (prev2, Mat[M - i - 1][cols])
			rows += 1
			cols += 1
		return Mat


class Solution:

	def rotateMatrix(self, m, n, l):
		top = 0
		bottom = m - 1
		left = 0
		right = n - 1
		while top < bottom and left < right:
			temp = l[top + 1][left]
			for i in range(left, right + 1):
				(l[top][i], temp) = (temp, l[top][i])
			top += 1
			for i in range(top, bottom + 1):
				(l[i][right], temp) = (temp, l[i][right])
			right -= 1
			for i in range(right, left - 1, -1):
				(l[bottom][i], temp) = (temp, l[bottom][i])
			bottom -= 1
			for i in range(bottom, top - 1, -1):
				(l[i][left], temp) = (temp, l[i][left])
			left += 1
		return l


class Solution:

	def rotateMatrix(self, M, N, Mat):
		(rowStart, rowEnd) = (0, M - 1)
		(colStart, colEnd) = (0, N - 1)
		while colStart < colEnd and rowStart < rowEnd:
			temp = Mat[rowStart][colEnd]
			for i in range(colEnd, colStart, -1):
				Mat[rowStart][i] = Mat[rowStart][i - 1]
			for i in range(rowStart, rowEnd):
				Mat[i][colStart] = Mat[i + 1][colStart]
			for i in range(colStart, colEnd):
				Mat[rowEnd][i] = Mat[rowEnd][i + 1]
			for i in range(rowEnd, rowStart + 1, -1):
				Mat[i][colEnd] = Mat[i - 1][colEnd]
			Mat[rowStart + 1][colEnd] = temp
			rowStart += 1
			colStart += 1
			rowEnd -= 1
			colEnd -= 1
		return Mat


class Solution:

	def rotateMatrix(self, M, N, mat):
		if not len(mat):
			return
		t = 0
		b = len(mat) - 1
		l = 0
		r = len(mat[0]) - 1
		while t < b and l < r:
			p = mat[t + 1][l]
			for i in range(l, r + 1):
				c = mat[t][i]
				mat[t][i] = p
				p = c
			t += 1
			for i in range(t, b + 1):
				c = mat[i][r]
				mat[i][r] = p
				p = c
			r -= 1
			for i in range(r, l - 1, -1):
				c = mat[b][i]
				mat[b][i] = p
				p = c
			b -= 1
			for i in range(b, t - 1, -1):
				c = mat[i][l]
				mat[i][l] = p
				p = c
			l += 1
		return mat


class Solution:

	def rotateMatrix(self, m, n, mat):
		top = 0
		left = 0
		right = n - 1
		bottom = m - 1
		while left < right and top < bottom:
			prev = mat[top + 1][left]
			for i in range(left, right + 1):
				curr = mat[top][i]
				mat[top][i] = prev
				prev = curr
			top += 1
			for i in range(top, bottom + 1):
				curr = mat[i][right]
				mat[i][right] = prev
				prev = curr
			right -= 1
			for i in range(right, left - 1, -1):
				curr = mat[bottom][i]
				mat[bottom][i] = prev
				prev = curr
			bottom -= 1
			for i in range(bottom, top - 1, -1):
				curr = mat[i][left]
				mat[i][left] = prev
				prev = curr
			left += 1
		return mat


class Solution:

	def rotateMatrix(self, N, M, matrix):
		i1 = j1 = 0
		i2 = 0
		j2 = M - 1
		i3 = N - 1
		j3 = M - 1
		i4 = N - 1
		j4 = 0
		if N == 1 or M == 1:
			return matrix
		while j1 < j2 and i1 < i4:
			try:
				a = i1
				b = j1
				c = i2
				d = j2
				e = i3
				f = j3
				g = i4
				h = j4
				temp = matrix[i1][j1]
				j1 += 1
				while j1 <= j2:
					temp1 = matrix[i1][j1]
					matrix[i1][j1] = temp
					temp = temp1
					j1 += 1
				i2 += 1
				while i2 <= i3:
					temp1 = matrix[i2][j2]
					matrix[i2][j2] = temp
					temp = temp1
					i2 += 1
				j3 -= 1
				while j3 >= j4:
					temp1 = matrix[i3][j3]
					matrix[i3][j3] = temp
					temp = temp1
					j3 -= 1
				i4 -= 1
				while i4 >= i1:
					temp1 = matrix[i4][j4]
					matrix[i4][j4] = temp
					temp = temp1
					i4 -= 1
				i1 = a + 1
				j1 = b + 1
				i2 = c + 1
				j2 = d - 1
				i3 = e - 1
				j3 = f - 1
				i4 = g - 1
				j4 = h + 1
			except:
				print('ohno')
		return matrix
import math
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, M) = map(int, input().strip().split(' '))
		A = []
		for i in range(N):
			B = list(map(int, input().strip().split(' ')))
			A.append(B)
		ob = Solution()
		ans = ob.rotateMatrix(N, M, A)
		for i in range(N):
			for j in range(M):
				print(ans[i][j], end=' ')
			print()


class Solution:

	def rotateMatrix(self, m, n, a):
		top = left = 0
		right = len(a[0]) - 1
		bottom = len(a) - 1
		while left < right and top < bottom:
			p = a[top + 1][left]
			for i in range(left, right + 1):
				c = a[top][i]
				a[top][i] = p
				p = c
			top += 1
			for i in range(top, bottom + 1):
				c = a[i][right]
				a[i][right] = p
				p = c
			right -= 1
			for i in range(right, left - 1, -1):
				c = a[bottom][i]
				a[bottom][i] = p
				p = c
			bottom -= 1
			for i in range(bottom, top - 1, -1):
				c = a[i][left]
				a[i][left] = p
				p = c
			left += 1
		return a


class Solution:

	def rotateMatrix(self, M, N, Mat):
		down = 0
		left = N
		up = M
		right = 0
		temp = 0
		i = 0
		bound = 0
		while i < M // 2 and i < N // 2:
			if left - 1 == right or up - 1 == down:
				break
			if bound < N:
				temp = Mat[bound][bound]
				bound += 1
			else:
				break
			for j in range(right + 1, left):
				temp_2 = Mat[down][j]
				Mat[down][j] = temp
				temp = temp_2
			for j in range(down + 1, up):
				temp_2 = Mat[j][left - 1]
				Mat[j][left - 1] = temp
				temp = temp_2
			for j in range(left - 2, right - 1, -1):
				temp_2 = Mat[up - 1][j]
				Mat[up - 1][j] = temp
				temp = temp_2
			for j in range(up - 2, down - 1, -1):
				temp_2 = Mat[j][right]
				Mat[j][right] = temp
				temp = temp_2
			down += 1
			left -= 1
			up -= 1
			right += 1
			i += 1
		return Mat


def get(mat, r1, c1, r2, c2):
	li = []
	for c in range(c1, c2 + 1):
		li.append(mat[r1][c])
	for r in range(r1 + 1, r2 + 1):
		li.append(mat[r][c2])
	for c in range(c2 - 1, c1 - 1, -1):
		li.append(mat[r2][c])
	for r in range(r2 - 1, r1, -1):
		li.append(mat[r][c1])
	return li

def put(mat, r1, c1, r2, c2, li):
	i = 0
	for c in range(c1, c2 + 1):
		mat[r1][c] = li[i]
		i += 1
	for r in range(r1 + 1, r2 + 1):
		mat[r][c2] = li[i]
		i += 1
	for c in range(c2 - 1, c1 - 1, -1):
		mat[r2][c] = li[i]
		i += 1
	for r in range(r2 - 1, r1, -1):
		mat[r][c1] = li[i]
		i += 1

class Solution:

	def rotateMatrix(self, M, N, Mat):
		(r1, c1, r2, c2) = (0, 0, M - 1, N - 1)
		while r1 < r2 and c1 < c2:
			li = get(Mat, r1, c1, r2, c2)
			li = [li[-1]] + li[:-1]
			put(Mat, r1, c1, r2, c2, li)
			r1 += 1
			r2 -= 1
			c1 += 1
			c2 -= 1
		return Mat


class Solution:

	def rotateMatrix(self, M, N, Mat):
		top = 0
		b = M - 1
		l = 0
		r = N - 1
		if N == 1 or M == 1:
			return Mat
		while top < b and l < r:
			b1 = Mat[top][r]
			for i in range(r, l, -1):
				Mat[top][i] = Mat[top][i - 1]
			b2 = Mat[b][r]
			for i in range(b, top, -1):
				Mat[i][r] = Mat[i - 1][r]
			Mat[top + 1][r] = b1
			b3 = Mat[b][l]
			for i in range(l, r):
				Mat[b][i] = Mat[b][i + 1]
			Mat[b][r - 1] = b2
			for i in range(top, b):
				Mat[i][l] = Mat[i + 1][l]
			Mat[b - 1][l] = b3
			top = top + 1
			b = b - 1
			l = l + 1
			r = r - 1
		return Mat


class Solution:

	def rotateMatrix(self, M, N, Mat):
		x = min(M, N) // 2
		for i in range(x):
			x = Mat[i][i]
			for j in range(i + 1, N - i):
				(x, Mat[i][j]) = (Mat[i][j], x)
			for j in range(i + 1, M - i):
				(x, Mat[j][N - i - 1]) = (Mat[j][N - i - 1], x)
			for j in range(N - i - 2, i - 1, -1):
				(x, Mat[M - i - 1][j]) = (Mat[M - i - 1][j], x)
			for j in range(M - i - 2, i - 1, -1):
				(x, Mat[j][i]) = (Mat[j][i], x)
		return Mat


class Solution:

	def rotateMatrix(self, M, N, mat):
		(top, left) = (0, 0)
		(bottom, right) = (M - 1, N - 1)
		while top < bottom and left < right:
			prev = mat[top + 1][left]
			for i in range(left, right + 1):
				cur = mat[top][i]
				mat[top][i] = prev
				prev = cur
			top += 1
			for i in range(top, bottom + 1):
				cur = mat[i][right]
				mat[i][right] = prev
				prev = cur
			right -= 1
			for i in range(right, left - 1, -1):
				cur = mat[bottom][i]
				mat[bottom][i] = prev
				prev = cur
			bottom -= 1
			for i in range(bottom, top - 1, -1):
				cur = mat[i][left]
				mat[i][left] = prev
				prev = cur
			left += 1
		return mat


import numpy as np

class Solution:

	def rotateMatrix(self, M, N, mat):
		if not len(mat):
			return
		top = 0
		bottom = len(mat) - 1
		left = 0
		right = len(mat[0]) - 1
		while left < right and top < bottom:
			prev = mat[top + 1][left]
			for i in range(left, right + 1):
				curr = mat[top][i]
				mat[top][i] = prev
				prev = curr
			top += 1
			for i in range(top, bottom + 1):
				curr = mat[i][right]
				mat[i][right] = prev
				prev = curr
			right -= 1
			for i in range(right, left - 1, -1):
				curr = mat[bottom][i]
				mat[bottom][i] = prev
				prev = curr
			bottom -= 1
			for i in range(bottom, top - 1, -1):
				curr = mat[i][left]
				mat[i][left] = prev
				prev = curr
			left += 1
		return mat


class Solution:

	def rotateMatrix(self, m, n, arr):
		top = 0
		left = 0
		right = n - 1
		bottom = m - 1
		i = 1
		while top < bottom and left < right:
			temp = arr[top][left]
			for p in range(left + 1, right + 1):
				(arr[top][p], temp) = (temp, arr[top][p])
			top += 1
			for q in range(top, bottom + 1):
				(arr[q][right], temp) = (temp, arr[q][right])
			right -= 1
			for p in range(right, left - 1, -1):
				(arr[bottom][p], temp) = (temp, arr[bottom][p])
			bottom -= 1
			for q in range(bottom, top - 1, -1):
				(arr[q][left], temp) = (temp, arr[q][left])
			left += 1
			arr[top - 1][left - 1] = temp
		return arr


class Solution:

	def rotateMatrix(self, M, N, mat):
		top = 0
		bottom = len(mat) - 1
		left = 0
		right = len(mat[0]) - 1
		while left < right and top < bottom:
			p = mat[top + 1][left]
			for i in range(left, right + 1):
				c = mat[top][i]
				mat[top][i] = p
				p = c
			top += 1
			for i in range(top, bottom + 1):
				c = mat[i][right]
				mat[i][right] = p
				p = c
			right -= 1
			for i in range(right, left - 1, -1):
				c = mat[bottom][i]
				mat[bottom][i] = p
				p = c
			bottom -= 1
			for i in range(bottom, top - 1, -1):
				c = mat[i][left]
				mat[i][left] = p
				p = c
			left += 1
		return mat


class Solution:

	def rotateMatrix(self, m, n, mat):
		if m == 1 or n == 1:
			return mat
		carry = mat[1][0]
		di = [0, 1, 0, -1]
		dj = [1, 0, -1, 0]
		ans = []
		vis = [[False for x in range(n)] for i in range(m)]
		(i, j) = (0, 0)
		cnt = 0
		for _ in range(min(n, m) // 2):
			carry = mat[i + 1][j]
			while True:
				temp = mat[i][j]
				mat[i][j] = carry
				carry = temp
				vis[i][j] = True
				newi = i + di[cnt]
				newj = j + dj[cnt]
				if newi < 0 or newi >= m or newj < 0 or (newj >= n) or (vis[newi][newj] == True):
					cnt = (cnt + 1) % 4
					i += di[cnt]
					j += dj[cnt]
					if cnt == 0:
						break
				else:
					i = newi
					j = newj
		return mat


class Solution:

	def rotateMatrix(self, m, n, mat):
		r = c = 0
		while r < m and c < n:
			if r + 1 == m or c + 1 == n:
				break
			prev = mat[r + 1][c]
			for i in range(c, n):
				(mat[r][i], prev) = (prev, mat[r][i])
			r += 1
			for j in range(r, m):
				(mat[j][n - 1], prev) = (prev, mat[j][n - 1])
			n -= 1
			if r < m:
				for i in range(n - 1, c - 1, -1):
					(mat[m - 1][i], prev) = (prev, mat[m - 1][i])
			m -= 1
			if c < n:
				for j in range(m - 1, r - 1, -1):
					(mat[j][c], prev) = (prev, mat[j][c])
			c += 1
		return mat


class Solution:

	def rotateMatrix(self, M, N, Mat):
		if not len(Mat):
			return
		left = 0
		right = N - 1
		top = 0
		bottom = M - 1
		while left < right and top < bottom:
			previous = Mat[top + 1][left]
			for i in range(left, right + 1):
				current = Mat[top][i]
				Mat[top][i] = previous
				previous = current
			top += 1
			for i in range(top, bottom + 1):
				current = Mat[i][right]
				Mat[i][right] = previous
				previous = current
			right -= 1
			for i in range(right, left - 1, -1):
				current = Mat[bottom][i]
				Mat[bottom][i] = previous
				previous = current
			bottom -= 1
			for i in range(bottom, top - 1, -1):
				current = Mat[i][left]
				Mat[i][left] = previous
				previous = current
			left += 1
		return Mat


class Solution:

	def rotateMatrix(self, M, N, mat):
		if len(mat) == 0:
			return 0
		top = 0
		bot = len(mat) - 1
		l = 0
		r = len(mat[0]) - 1
		while l < r and top < bot:
			prev = mat[top + 1][l]
			for i in range(l, r + 1):
				curr = mat[top][i]
				mat[top][i] = prev
				prev = curr
			top += 1
			for i in range(top, bot + 1):
				curr = mat[i][r]
				mat[i][r] = prev
				prev = curr
			r -= 1
			for i in range(r, l - 1, -1):
				curr = mat[bot][i]
				mat[bot][i] = prev
				prev = curr
			bot -= 1
			for i in range(bot, top - 1, -1):
				curr = mat[i][l]
				mat[i][l] = prev
				prev = curr
			l += 1
		return mat


class Solution:

	def rotateMatrix(self, M, N, Mat):
		l = 0
		r = N - 1
		t = 0
		b = M - 1
		while l < r and t < b:
			p = Mat[t + 1][l]
			for i in range(l, r + 1):
				(Mat[t][i], p) = (p, Mat[t][i])
			t += 1
			for i in range(t, b + 1):
				(Mat[i][r], p) = (p, Mat[i][r])
			r -= 1
			for i in range(r, l - 1, -1):
				(Mat[b][i], p) = (p, Mat[b][i])
			b -= 1
			for i in range(b, t - 1, -1):
				(Mat[i][l], p) = (p, Mat[i][l])
			l += 1