from __future__ import print_function # Time: O(n^2) # Space: O(1) # # You are given an n x n 2D matrix representing an image. # # Rotate the image by 90 degrees (clockwise). # # Follow up: # Could you do this in-place? # # Time: O(n^2) # Space: O(1) class Solution: # @param matrix, a list of lists of integers # @return a list of lists of integers def rotate(self, matrix): n = len(matrix) # anti-diagonal mirror for i in xrange(n): for j in xrange(n - i): matrix[i][j], matrix[n-1-j][n-1-i] = matrix[n-1-j][n-1-i], matrix[i][j] # horizontal mirror for i in xrange(n / 2): for j in xrange(n): matrix[i][j], matrix[n-1-i][j] = matrix[n-1-i][j], matrix[i][j] return matrix # Time: O(n^2) # Space: O(n^2) class Solution2: # @param matrix, a list of lists of integers # @return a list of lists of integers def rotate(self, matrix): return [list(reversed(x)) for x in zip(*matrix)] if __name__ == "__main__": matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] print(Solution().rotate(matrix))