Flipping an Image

#881 Most AskedEasy

Flipping an Image #881 Most Asked

Easy

7 views

Topics:

ArraysBit Manipulation

Given an n x n binary matrix image, flip the image horizontally, then invert it, and return the resulting image.

To flip an image horizontally means that each row of the image is reversed.

For example, flipping [1,1,0] horizontally results in [0,1,1].

To invert an image means that each 0 is replaced by 1, and each 1 is replaced by 0.

For example, inverting [0,1,1] results in [1,0,0].

Example 1:

Input: image = [[1,1,0],[1,0,1],[0,0,0]]
Output: [[1,0,0],[0,1,0],[1,1,1]]
Explanation: First reverse each row: [[0,1,1],[1,0,1],[0,0,0]].
Then, invert the image: [[1,0,0],[0,1,0],[1,1,1]]

Example 2:

Input: image = [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]
Output: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
Explanation: First reverse each row: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]].
Then invert the image: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]

Constraints:

n == image.length
n == image[i].length
1 <= n <= 20
images[i][j] is either 0 or 1.

Try coding it in LeetCode

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 are the dimensions of the input `image` matrix? Are there any constraints on the number of rows or columns?
What data type are the elements within the `image` matrix (e.g., integer, boolean)? Is it guaranteed to be binary (only 0s and 1s)?
Can the input `image` be empty (i.e., have zero rows or columns)? If so, what should the function return?
Does the `image` matrix need to be a square matrix, or can it be rectangular (different number of rows and columns)?
Is the modification of the input `image` matrix in place allowed, or should I create a new matrix to store the flipped and inverted image?

Brute Force Solution

Approach

The brute force approach to flipping an image involves directly manipulating each row and then swapping elements within each row. We meticulously apply each transformation and reflect the outcome in the final result. Essentially, we perform each required action, one step at a time, across the entire image.

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

For each row of the image, we will perform the following steps.
First, reverse the order of elements in that row.
Next, look at each element in the reversed row.
If the element is a zero, change it to a one.
If the element is a one, change it to a zero.
After going through all rows and elements, you will have the flipped image.

Code Implementation

def flip_an_image(image):
    flipped_image = []

    for row in image:
        # Create a new row, reversing the elements
        reversed_row = row[::-1]

        # Create a new list to hold the flipped row
        flipped_row = []
        for element in reversed_row:
            # Invert the bit
            if element == 0:
                flipped_row.append(1)
            else:
                flipped_row.append(0)
        
        flipped_image.append(flipped_row)
    
    return flipped_image

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n rows in the image. Inside the outer loop, the algorithm reverses each row, which takes O(n) time where n represents the number of elements in the row (which is also the image's width). Then, it iterates through each of the n elements in the reversed row to flip the bits (0 to 1, or 1 to 0), which also takes O(n) time. Therefore, since both the reversal and the bit flipping are nested within the outer loop that iterates through the rows, the overall time complexity is n * (n + n), which simplifies to approximately n * 2n, further simplifying to O(n²).

Space Complexity

O(1) – The provided algorithm operates in place, modifying the input image directly. No auxiliary data structures like new arrays or hash maps are created to store intermediate results. The only extra memory used is for a few temporary variables to facilitate element swapping during the reversal and bit flipping, and their number remains constant irrespective of the image size N, where N is the number of rows times the number of columns. Therefore, the space complexity is constant.

Optimal Solution

Approach

To flip the image efficiently, we can think of it as two separate operations: reversing each row and then inverting the colors. Reversing swaps elements in each row, and inverting changes 0s to 1s and vice versa.

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

For each row in the image, reverse the order of the elements.
Within each row, change all the 0s to 1s and all the 1s to 0s.

Code Implementation

def flip_image(image): 
    for row in image:
        # Reversing the row is the first step.
        row.reverse()

        for i in range(len(row)):
            # Invert each pixel by XORing with 1.
            row[i] ^= 1

    return image

Big(O) Analysis

Time Complexity

O(n²) – The outer loop iterates through each of the 'n' rows in the image. Inside this loop, we reverse the elements of each row, which takes approximately n/2 operations where 'n' represents the number of columns. Then, we iterate through each of the 'n' elements in that same row to invert the color, also taking 'n' operations. Thus, the dominant operations approximate n * (n/2 + n) operations which simplifies to O(n²).

Space Complexity

O(1) – The algorithm operates directly on the input image array, modifying it in place. There is no creation of any auxiliary data structures such as temporary arrays or hash maps to store intermediate results during the reversing and inverting steps. Therefore, the space used remains constant irrespective of the size of the input image represented by N (where N is the total number of elements in the image). This makes the auxiliary space complexity O(1).

Edge Cases

Case	How to Handle
Null or Empty input matrix	Return an empty list or null if the input matrix is null or has zero rows.
Matrix with only one row	Handle the horizontal flip and inversion on the single row correctly.
Matrix with only one column	The horizontal flip won't change the column, but the inversion must still be performed.
Square matrix with dimensions nearing integer limits (large N)	Ensure that memory allocation and row/column operations do not lead to integer overflow or excessive memory usage.
All elements in the matrix are 0	The inversion will change all elements to 1, handled correctly by the inversion logic.
All elements in the matrix are 1	The inversion will change all elements to 0, handled correctly by the inversion logic.
Non-square matrix	The solution should work correctly regardless of the number of rows and columns, flipping each row independently.
Input matrix is not a valid binary matrix (contains values other than 0 or 1)	The inversion logic may produce unexpected results, so validation of input might be required.

Null or Empty input matrix

How to Handle:

Return an empty list or null if the input matrix is null or has zero rows.

Matrix with only one row

How to Handle:

Handle the horizontal flip and inversion on the single row correctly.

Matrix with only one column

How to Handle:

The horizontal flip won't change the column, but the inversion must still be performed.

Square matrix with dimensions nearing integer limits (large N)

How to Handle:

Ensure that memory allocation and row/column operations do not lead to integer overflow or excessive memory usage.

All elements in the matrix are 0

How to Handle:

The inversion will change all elements to 1, handled correctly by the inversion logic.

All elements in the matrix are 1

How to Handle:

The inversion will change all elements to 0, handled correctly by the inversion logic.

Non-square matrix

How to Handle:

The solution should work correctly regardless of the number of rows and columns, flipping each row independently.

Input matrix is not a valid binary matrix (contains values other than 0 or 1)

How to Handle:

The inversion logic may produce unexpected results, so validation of input might be required.