Rotate Matrix

Edit PagePage History

JCSU Unit 5 Problem Set 1 (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 20 mins
• 🛠️ Topics: Matrix Manipulation, Transpose, Nested Lists

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• What is the goal of the problem?
  • Rotate a square matrix 90 degrees clockwise.
• Are there constraints on input?
  • Input may be an empty matrix, a 1x1 matrix, or larger n x n matrices.

HAPPY CASE Input: matrix = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ] Output: [ [7, 4, 1], [8, 5, 2], [9, 6, 3] ] Explanation: The matrix is rotated 90 degrees clockwise by reversing columns and transposing rows.

EDGE CASE Input: matrix = [ [1] ] Output: [ [1] ] Explanation: A 1x1 matrix remains unchanged.

EDGE CASE Input: matrix = [] Output: [] Explanation: An empty matrix results in an empty output.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For matrix rotation problems, we want to consider the following approaches:

• Transpose and Reverse Columns: Use zip() to transpose the matrix and reverse the rows to achieve rotation.
• In-place Rotation (Alternative): For large matrices, consider modifying the matrix directly to reduce space usage.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
Use the zip() function to transpose the rows into columns and reverse them to achieve a 90-degree rotation.

Steps:

1. Check if the input matrix is empty or its first row is empty. If so, return an empty list.
2. Use zip(*matrix) to transpose the rows into columns.
3. Reverse the order of elements in each column to rotate 90 degrees clockwise.
4. Convert the result of zip() into a list of lists and return it.

4: I-mplement

Implement the code to solve the algorithm.

def rotate_matrix_90(matrix):
    if not matrix or not matrix[0]:  # Check for an empty matrix
        return []  # Return an empty matrix if input is empty

    # Use zip to transform rows into columns, reversed to rotate 90 degrees clockwise
    rotated = [list(reversed(col)) for col in zip(*matrix)]
    return rotated  # Return the rotated matrix

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

Example 1:

• Input: matrix = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ]
• Expected Output: [ [7, 4, 1], [8, 5, 2], [9, 6, 3] ]
• Observed Output: [ [7, 4, 1], [8, 5, 2], [9, 6, 3] ]

Example 2:

• Input: matrix = [ [1] ]
• Expected Output: [ [1] ]
• Observed Output: [ [1] ]

Example 3:

• Input: matrix = []
• Expected Output: []
• Observed Output: []

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume n is the number of rows (or columns) in the matrix.

• Time Complexity: O(n^2) because we iterate through all elements of the matrix during the transpose and reversal.
• Space Complexity: O(n^2) because we create a new matrix for the rotated result.