Math and Geometry

Question 1

Rotate an n x n array in place.

Answer 1

• Swap matrix[row][col] with matrix[col][row] but don’t let the inner loop double swap.
• Reverse each row in the outer loop.

def rotate(self, matrix: List[List[int]]) -> None:
for i in range(len(matrix)):
for j in range(i, len(matrix)):
temp = matrix[i][j]
matrix[i][j] = matrix[j][i]
matrix[j][i] = temp
matrix[i].reverse()

    return matrix

Question 2

Given an m x n matrix, return all elements of the matrix in spiral order.

Answer 2

Set top, bottom, left, right pointers.
bottom and right need to be outside the range

• While these pointers don’t equal each other…use 4 for loops like:
• for i in range(top, right): …..
• then reduce the pointers every time you finish a row or column
• You have to break the loop in the middle when the some pointers equal each other, or you’ll get duplicates.
• Alternatively, you can use a visited set and check when things are out of bounds and go in R D L U order…..

Question 3

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0’s.

You must do it in place.

Can you do it in O(1) space complexity?

Answer 3

• O(m*n) / O(m + n) solution is easy - just iterate through the matrix and store each column and row that needs to be 0’ed in it’s respective set.
• You can do this in O(1) space complexity by marks 0’s in the top row and left column for those that need to be 0’ed.
• Just mark the first row as True or False in a separate variable and zero this one out last to prevent conflicts.