LeetCode #48: Rotate Image

https://leetcode.com/problems/rotate-image/

To rotate a matrix in-place by 90 degrees, we will use a nested loop to iterate over each of the four edges of the matrix. We will start with the outermost edge and work our way inwards. For each element in an edge, we will perform a series of swaps to rotate the element to its new position.

The swaps we will perform are:

matrix[top][left + i], matrix[bottom - i][left], matrix[bottom][right - i], matrix[top + i][right]

where top is the index of the first row in the edge, bottom is the index of the last row in the edge, left is the index of the first column in the edge, right is the index of the last column in the edge, and i is the index of the current element in the edge.

We will perform this swap for each element in the edge, and then move to the next edge. We will continue this process until we have rotated all four edges.

1. Initialize left to 0 and right to n-1, where n is the length of the matrix.
2. While left < right, do the following:
   1. For i in range(right - left), do the following:
      1. Initialize top to left and bottom to right.
      2. Save the value of matrix[top][left + i] to a variable called temp.
      3. Set matrix[top][left + i] to matrix[bottom - i][left].
      4. Set matrix[bottom - i][left] to matrix[bottom][right - i].
      5. Set matrix[bottom][right - i] to matrix[top + i][right].
      6. Set matrix[top + i][right] to temp.
   2. Increment left by 1 and decrement right by 1.

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        l, r = 0, len(matrix) - 1
        while l < r:
            for i in range(r - l):
                top, bottom = l, r

                # save the topleft
                topLeft = matrix[top][l + i]

                # move bottom left into top left
                matrix[top][l + i] = matrix[bottom - i][l]

                # move bottom right into bottom left
                matrix[bottom - i][l] = matrix[bottom][r - i]

                # move top right into bottom right
                matrix[bottom][r - i] = matrix[top + i][r]

                # move top left into top right
                matrix[top + i][r] = topLeft
            r -= 1
            l += 1

Time and Space Complexity

The time complexity of the given solution is O(n^2), where n is the number of rows or columns in the matrix. This is because we are iterating through each element in the matrix and performing a constant number of operations (5 in this case) on each element.

The space complexity of the solution is O(1), since we are modifying the matrix in-place and not using any extra data structures that scale with the input size. Therefore, the space used is constant and does not depend on the input size.