Jobs

Interviews

Discussions

Rotate Image

Medium

Netflix

0 views

Topics:

Arrays

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do 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 == matrix.length == matrix[i].length
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000

Rotate Image

Medium

Netflix

0 views

Topics:

Arrays

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do 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 == matrix.length == matrix[i].length
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the size limit of the square matrix? For example, what is the maximum value of 'n' where the matrix is n x n?
Are the integer values within the matrix constrained to a specific range? Are negative values allowed?
Is the input matrix guaranteed to be a square matrix, or should I handle cases where the number of rows and columns are different?
By 'in-place', are we strictly limited to O(1) extra space, or can we use a small, constant amount of additional memory?
If the input matrix is empty (n=0), what should happen? Should I throw an exception, or is no action required?

Brute Force Solution

Approach

The brute force method to rotate an image involves creating a completely new image and copying the values from the original image to the correct rotated positions in the new image. This approach directly moves each value without trying to optimize the process, checking every single position.

Here's how the algorithm would work step-by-step:

First, create a brand new, empty image with the same size as the original image.
Next, go through each location in the original image, one by one.
For each location in the original image, figure out where that value should end up in the rotated image.
Copy the value from that original location to its corresponding rotated location in the new image.
Repeat this process for every single location in the original image, until all values have been copied to their new rotated positions in the new image.
Finally, replace the original image with this new, rotated image.

Code Implementation

def rotate_image_brute_force(image):
    matrix_size = len(image)

    # Create a new matrix to store the rotated image
    rotated_image = [[0] * matrix_size for _ in range(matrix_size)]

    for row in range(matrix_size):
        for column in range(matrix_size):

            # Calculate the new row and column after rotation
            new_row = column
            new_column = matrix_size - 1 - row

            # Place the element in the correct position in the rotated image
            rotated_image[new_row][new_column] = image[row][column]

    # Replace the original image with the rotated image
    for row in range(matrix_size):
        for column in range(matrix_size):
            image[row][column] = rotated_image[row][column]

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each element of the n x n image to copy it to its rotated position. This involves accessing each of the n rows and n columns in the original image. For every element in the original image, a corresponding placement is made in the new image. Thus the operations are proportional to the number of elements in the image which is n*n. Therefore, the time complexity is O(n²).

Space Complexity

O(N^2) – The provided solution creates a new image with the same dimensions as the original image. If the original image is N x N, then the new image also has N x N elements. This new image is an auxiliary data structure that requires space proportional to the number of elements, resulting in a space complexity of O(N^2).

Optimal Solution

Approach

Rotating an image efficiently involves two key transformations done in place. First, we flip the image along its main diagonal. Then, we flip the image horizontally to achieve the desired 90-degree clockwise rotation.

Here's how the algorithm would work step-by-step:

Imagine drawing a line from the top-left corner to the bottom-right corner of the image; this is the main diagonal.
Swap the elements of the image that are on opposite sides of this diagonal; this is like reflecting the image across this diagonal.
Next, for each row in the image, reverse the order of the elements; this is like flipping each row horizontally.
After these two steps, the image will be rotated 90 degrees clockwise.

Code Implementation

def rotate_image(matrix):
    matrix_size = len(matrix)

    # Transpose the matrix (flip over main diagonal)
    for i in range(matrix_size):
        for j in range(i, matrix_size):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

    # Reflect each row horizontally
    # This completes the 90-degree clockwise rotation
    for row in matrix:
        row.reverse()

    #Horizontal flip is necessary for clockwise rotation.
    return matrix

Big(O) Analysis

Time Complexity

O(n²) – The first part of the algorithm flips the image along its main diagonal. This involves iterating through roughly the upper triangle of the n x n matrix, resulting in approximately n * n/2 operations where n is the number of rows (or columns) in the image. The second part flips the image horizontally row by row, and this takes approximately n * n/2 operations because we iterate through n rows and in each row we iterate through half the row. Summing them up provides n² operations, which simplifies to O(n²).

Space Complexity

O(1) – The algorithm operates in-place, modifying the input matrix directly. It only uses a few temporary variables for swapping elements during both the diagonal flip and the horizontal flip. The number of these variables doesn't depend on the size of the input image, which we can denote as an NxN matrix. Therefore, the auxiliary space used is constant, independent of the input size N.

Edge Cases

Case	How to Handle
Null or empty matrix	Check for null or empty matrix and return immediately if true to avoid NullPointerException or errors.
Non-square matrix	Throw an IllegalArgumentException, or return false/error code, because the rotation is undefined for non-square matrices.
1x1 matrix	The rotation does nothing, so return immediately as it's already rotated.
2x2 matrix	The standard in-place rotation algorithm should correctly handle this minimum size efficiently.
Matrix with Integer.MAX_VALUE or Integer.MIN_VALUE	The in-place rotation does not perform arithmetic operations that can overflow; it only involves swapping values so it's safe.
Large matrix (e.g., 1000x1000) exceeding memory constraints	The in-place rotation algorithm operates within the original matrix, minimizing memory usage and avoiding excessive memory allocation.
Matrix contains all identical values	The algorithm should still correctly rotate the image regardless of the element values within the matrix.
Matrix contains negative numbers, zeros, and positive numbers	The in-place rotation operates on indices and swapping, so the algorithm will function correctly regardless of the matrix's number distribution.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the size limit of the square matrix? For example, what is the maximum value of 'n' where the matrix is n x n?
Are the integer values within the matrix constrained to a specific range? Are negative values allowed?
Is the input matrix guaranteed to be a square matrix, or should I handle cases where the number of rows and columns are different?
By 'in-place', are we strictly limited to O(1) extra space, or can we use a small, constant amount of additional memory?
If the input matrix is empty (n=0), what should happen? Should I throw an exception, or is no action required?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, create a brand new, empty image with the same size as the original image.
Next, go through each location in the original image, one by one.
For each location in the original image, figure out where that value should end up in the rotated image.
Copy the value from that original location to its corresponding rotated location in the new image.
Repeat this process for every single location in the original image, until all values have been copied to their new rotated positions in the new image.
Finally, replace the original image with this new, rotated image.

Code Implementation

def rotate_image_brute_force(image):
    matrix_size = len(image)

    # Create a new matrix to store the rotated image
    rotated_image = [[0] * matrix_size for _ in range(matrix_size)]

    for row in range(matrix_size):
        for column in range(matrix_size):

            # Calculate the new row and column after rotation
            new_row = column
            new_column = matrix_size - 1 - row

            # Place the element in the correct position in the rotated image
            rotated_image[new_row][new_column] = image[row][column]

    # Replace the original image with the rotated image
    for row in range(matrix_size):
        for column in range(matrix_size):
            image[row][column] = rotated_image[row][column]

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine drawing a line from the top-left corner to the bottom-right corner of the image; this is the main diagonal.
Swap the elements of the image that are on opposite sides of this diagonal; this is like reflecting the image across this diagonal.
Next, for each row in the image, reverse the order of the elements; this is like flipping each row horizontally.
After these two steps, the image will be rotated 90 degrees clockwise.

Code Implementation

def rotate_image(matrix):
    matrix_size = len(matrix)

    # Transpose the matrix (flip over main diagonal)
    for i in range(matrix_size):
        for j in range(i, matrix_size):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

    # Reflect each row horizontally
    # This completes the 90-degree clockwise rotation
    for row in matrix:
        row.reverse()

    #Horizontal flip is necessary for clockwise rotation.
    return matrix

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty matrix	Check for null or empty matrix and return immediately if true to avoid NullPointerException or errors.
Non-square matrix	Throw an IllegalArgumentException, or return false/error code, because the rotation is undefined for non-square matrices.
1x1 matrix	The rotation does nothing, so return immediately as it's already rotated.
2x2 matrix	The standard in-place rotation algorithm should correctly handle this minimum size efficiently.
Matrix with Integer.MAX_VALUE or Integer.MIN_VALUE	The in-place rotation does not perform arithmetic operations that can overflow; it only involves swapping values so it's safe.
Large matrix (e.g., 1000x1000) exceeding memory constraints	The in-place rotation algorithm operates within the original matrix, minimizing memory usage and avoiding excessive memory allocation.
Matrix contains all identical values	The algorithm should still correctly rotate the image regardless of the element values within the matrix.
Matrix contains negative numbers, zeros, and positive numbers	The in-place rotation operates on indices and swapping, so the algorithm will function correctly regardless of the matrix's number distribution.