Complexity Analysis
def rotate_matrix(matrix):
n = len(matrix)
for i in range(n):
for j in range(i, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
for row in matrix:
row.reverse()What is the time and space complexity?
Work it out before scrolling down.
Time
O(n²)
Space
O(1)
How to derive it
First nested loop: triangular traversal = n(n+1)/2 = O(n²) swaps. Second loop: n rows, each reversed in O(n) = O(n²). Total: O(n²). Here n is the matrix dimension, so n² is the total number of elements — you must touch every element at least once, making O(n²) optimal. In-place swaps → O(1) extra space.