Rotate A Square Grid
Problem
Turn an n by n grid a quarter turn clockwise, so the first column read from the bottom up becomes the first row. Do it in place, rearranging values inside the grid you were given rather than building a second grid.
Examples
Input: grid = [[1, 2, 3],
[4, 5, 6],
[7, 8, 9]]
Output: [[7, 4, 1],
[8, 5, 2],
[9, 6, 3]]Input: grid = [[1, 2],
[3, 4]]
Output: [[3, 1],
[4, 2]]Input: grid = [[7]]
Output: [[7]]
Why: edge case, a single cell turns into itselfHints
0 / 3
Moving each value straight to its final place overwrites a value you still need. Look for simpler moves that are easy to do in place and add up to a quarter turn.
Two in-place operations are cheap on a square grid: flipping across the main diagonal, which swaps each cell at row r, column c with the one at row c, column r, and reversing each row.
First swap every cell above the main diagonal with its mirror below it. Then reverse every row. The combination is exactly a clockwise quarter turn.
Solution
A clockwise quarter turn sends the cell at row r, column c to row c, column n minus 1 minus r. Flipping across the main diagonal sends it to row c, column r, and reversing each row then sends that to row c, column n minus 1 minus r, which is the same destination. Both steps are made of swaps that never need a second grid; the flip only visits cells above the diagonal so each pair is swapped once. Every cell is touched a constant number of times, so time is O(n squared) and extra space is O(1).
def rotate_clockwise(grid):
n = len(grid)
for r in range(n):
for c in range(r + 1, n): # above the diagonal only, once per pair
grid[r][c], grid[c][r] = grid[c][r], grid[r][c]
for row in grid:
row.reverse() # mirror each row left to right
return grid
print(rotate_clockwise([[1, 2, 3], [4, 5, 6], [7, 8, 9]])) # -> [[7, 4, 1], [8, 5, 2], [9, 6, 3]]
print(rotate_clockwise([[1, 2], [3, 4]])) # -> [[3, 1], [4, 2]]
print(rotate_clockwise([[7]])) # -> [[7]]Stuck on the idea rather than the code? Rotate In Place covers it.