Rotate Image Leetcode Problem 48 [Python Solution]

In this blog post, we'll tackle the Rotate Image problem from LeetCode, specifically Problem 48. This problem falls under the category of Math and Geometry and is rated as a medium difficulty problem.

The goal is to rotate a given n x n 2D matrix, representing an image, by 90 degrees clockwise.

Importantly, we must perform this rotation in-place, which means we're not allowed to allocate another 2D matrix and must modify the input matrix directly.

Before diving into the solution, let's understand the problem in detail.

Problem Overview

You are given an n x n 2D matrix representing an image, and your task is to rotate this image by 90 degrees clockwise.

The rotation should occur in-place, meaning you must modify the input 2D matrix directly.

Here's an example to illustrate the rotation:

Example 1:

Input:

matrix = [[1,2,3],
[4,5,6],
[7,8,9]]


Output:

[[7,4,1],
[8,5,2],
[9,6,3]]


Example 2:

Input:

matrix = [[5,1,9,11],
[2,4,8,10],
[13,3,6,7],
[15,14,12,16]]


Output:

[[15,13,2,5],
[14,3,4,1],
[12,6,8,9],
[16,7,10,11]]


Constraints:

• n is the number of rows and columns in the matrix.
• 1 <= n <= 20
• -1000 <= matrix[i][j] <= 1000

Now that we understand the problem, let's delve into the solution.

Understanding Constraints

Before we jump into the solution, let's briefly discuss the constraints provided in the problem.

Understanding these constraints is essential for designing an efficient solution.

In this case, the most critical constraint is the in-place requirement.

We must perform the rotation within the given matrix without using additional memory.

Additionally, we're given the range of values in the matrix, which helps us understand the data we're working with.

Rotate Image LeetCode Problem Solution

1. Bruteforce Approach

Let's start by discussing a straightforward approach to solving this problem.

We can perform the rotation layer by layer, starting from the outermost layer and moving towards the center of the matrix.

1. Initialize the left boundary left to 0 and the right boundary right to n - 1, where n is the number of rows (or columns) in the matrix.

2. Iterate through the layers of the matrix.

For each layer, perform the following rotations:

• Iterate through the elements in the top row of the current layer (from left to right - 1).
• For each element, save the top-left value in a temporary variable.
• Move the bottom-left value to the top-left position.
• Move the bottom-right value to the bottom-left position.
• Move the top-right value to the bottom-right position.

• Move the temporary variable (the original top-left value) to the top-right position.

1. After completing the rotations for the current layer, increment left and decrement right to move to the next inner layer.

2. Repeat steps 2 and 3 until left is no longer less than right.

This ensures that we process all layers.

Here's the Python code for this brute-force approach:

def rotate(matrix):
    n = len(matrix)
    left, right = 0, n - 1

    while left < right:
        for i in range(right - left):
            top, bottom = left, right
            topLeft = matrix[top][left + i]
            matrix[top][left + i] = matrix[bottom - i][left]
            matrix[bottom - i][left] = matrix[bottom][right - i]
            matrix[bottom][right - i] = matrix[top + i][right]
            matrix[top + i][right] = topLeft
        right -= 1
        left += 1

This brute-force approach works and provides the correct result.

However, it may seem a bit complex due to the layer-by-layer rotation.

So, let's explore a more efficient approach to this problem.

2. An Efficient Approach with a Single Loop

While the brute-force approach is correct, we can simplify our solution by using a single loop.

This approach is more intuitive and straightforward to implement.

Here's the Python code for this efficient approach:

def rotate(matrix):
    n = len(matrix)

    for i in range(n // 2):
        for j in range(i, n - i - 1):
            temp = matrix[i][j]
            matrix[i][j] = matrix[n - j - 1][i]
            matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1]
            matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1]
            matrix[j][n - i - 1] = temp

This approach simplifies the rotation by iterating through the matrix once and performing the swaps directly.

The outer loop handles the layers, and the inner loop performs the four-element swaps for each layer.

It's a more elegant and efficient solution.

Rotate Image Python Code Solution

Let's provide the complete Python code solution based on the efficient approach:

def rotate(matrix):
    n = len(matrix)

    for i in range(n // 2):
        for j in range(i, n - i - 1):
            temp = matrix[i][j]
            matrix[i][j] = matrix[n - j - 1][i]
            matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1]
            matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1]
            matrix[j][n - i - 1] = temp

This code performs the matrix rotation efficiently in place, adhering to the problem's constraints.

Time and Space Complexity

Now, let's analyze the time and space complexity of our efficient solution:

Time Complexity: Our approach iterates through the matrix once.

The loop performs a constant number of operations for each element, making the time complexity O(n^2), where n is the number of rows or columns in the matrix.

Space Complexity: Our approach uses only a constant amount of extra space, making the space complexity O(1).

Reasoning Behind Our Approach

The efficient approach simplifies the problem by iteratively swapping the elements in the matrix.

The main idea is to rotate the elements in a single pass, ensuring that we correctly update each element without losing any values.

This approach reduces the complexity of the problem while adhering to the in-place constraint.

Related Interview Questions By Company:

• Lru Cache LeetCode
• Unique Paths LeetCode
• Sort Colors LeetCode

Related Interview Questions By Difficulty:

• Rotate Image LeetCode
• Integer To Roman LeetCode
• Set Matrix Zeroes LeetCode

Related Interview Questions By Category:

• Multiply Strings LeetCode
• Find Pivot Index LeetCode
• Count Good Nodes In Binary Tree LeetCode

Conclusion

In this blog post, we addressed the Rotate Image problem from LeetCode, providing both

a brute-force approach and a more efficient solution.

The efficient approach simplifies the rotation process by using a single loop to perform in-place swaps, making it a cleaner and more intuitive solution.

We encourage you to try out the provided Python code solutions on the LeetCode platform to gain a deeper understanding and further improve your coding skills.

If you found this post helpful, please like and engage to support our content.

Additionally, feel free to comment, ask questions, make suggestions, or share this content with others who might find it beneficial.

Question Link: Rotate Image LeetCode Problem

Happy coding!