Instantly share code, notes, and snippets.

# arjun-menon/rotate_matrix.py

Last active January 10, 2016 10:19
Show Gist options
• Save arjun-menon/0348ed18f573f20601b5 to your computer and use it in GitHub Desktop.
Rotate a matrix clockwise by 90 degrees
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 """ Rotate a matrix clockwise by 90 degrees """ def iter_matrix_outline(n): for j in range(0, n): yield (0, j) for i in range(1, n): yield (i, n-1) for j in range(n-2, -1, -1): yield (n-1, j) for i in range(n-2, 0, -1): yield (i, 0) raise StopIteration def shift_outline_by_one(mat, n, start_offset=0): prev = None for k in iter_matrix_outline(mat, n): if k == (0, 0): prev = mat[start_offset][start_offset] continue current = mat[ start_offset+k[0] ][ start_offset+k[1] ] mat[ start_offset+k[0] ][ start_offset+k[1] ] = prev prev = current mat[start_offset][start_offset] = prev def rotate_matrix(mat): n = len(mat) start_offset = 0 while n >= 2: for i in range(n-1): shift_outline_by_one(mat, n, start_offset) start_offset += 1 n -= 2 if __name__ == '__main__': p1 = [ ['A','B','C','D', 'E'], ['F','G','H','I', 'J'], ['K','L','M','N', 'O'], ['P','Q','R','S', 'T'], ['U','V','W','X', 'Y'] ] p2 = [ ['A','B','C','D'], ['E','F','G','H'], ['I','J','K','L'], ['M','N','O','P'], ] p3 = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ] p4 = [ [1, 2], [3, 4], ] p5 = [ [5], ] problems = [p1, p2, p3, p4, p5] def disp(mat): print('\n'.join(' '.join(str(i) for i in row) for row in mat)) def test_iter_matrix_outline(mat): for k in iter_matrix_outline(len(mat)): print(k, " -> ", mat[k[0]][k[1]]) def solve_problem(mat): print("Original:") disp(mat) print("Rotated:") rotate_matrix(mat) disp(mat) for p in problems: print() solve_problem(p) print()

### arjun-menon commented Jan 10, 2016

For a n x n matrix, this implementation has space complexity of O(1), and a time complexity that is likely O(n^2 * log(n))...

to join this conversation on GitHub. Already have an account? Sign in to comment