Flipping an Image

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.

def flipAndInvertImage(image):
    """
    Flips the image horizontally and then inverts it.

    Args:
        image (List[List[int]]): The input n x n binary matrix.

    Returns:
        List[List[int]]: The resulting image after flipping and inverting.
    """
    n = len(image)
    for i in range(n):
        # Reverse the row
        image[i] = image[i][::-1]
        # Invert the row
        for j in range(n):
            image[i][j] = 1 - image[i][j]
    return image

# Example usage:
image1 = [[1,1,0],[1,0,1],[0,0,0]]
print(flipAndInvertImage(image1))  # Output: [[1,0,0],[0,1,0],[1,1,1]]

image2 = [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]
print(flipAndInvertImage(image2))  # Output: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]

Explanation:

The function flipAndInvertImage takes an n x n binary matrix called image as input. It performs two operations on the image:

1. Horizontal Flip: For each row in the image, it reverses the order of elements.
2. Invert: For each element (pixel) in the flipped image, it changes 0 to 1 and 1 to 0.

The function then returns the modified image.

Naive Solution:

A naive solution would involve creating a new matrix to store the flipped and inverted image. This would require additional space.

def flipAndInvertImage_naive(image):
    n = len(image)
    result = [([0] * n) for _ in range(n)] # Create a new matrix
    for i in range(n):
        for j in range(n):
            result[i][j] = 1 - image[i][n - 1 - j] # Flip and invert
    return result

This naive solution has a space complexity of O(n^2) because a completely new n x n matrix needs to be created.

Optimal Solution:

The provided solution is optimal because it performs the operations in-place, modifying the original matrix directly. This avoids the extra space required by the naive solution.

Big(O) Run-time Analysis:

The outer loop iterates n times (once for each row). The inner loop also iterates n times (once for each element in the row). The reversing operation image[i] = image[i][::-1] takes O(n) time. Because this happens n times, the total time is O(n^2). Therefore, the overall time complexity is O(n^2).

Big(O) Space Usage Analysis:

The algorithm operates in-place, modifying the original matrix. No additional data structures that scale with the input size are created. Therefore, the space complexity is O(1) (constant).

Edge Cases:

1. Empty Image: If the input image is empty (n=0), the code will still work correctly because the loops will not execute.
2. Image with One Row/Column: If the image has only one row or one column, the flipping and inverting operations will still be performed correctly.
3. Non-Binary Image: If the image contains values other than 0 and 1, the inverting operation 1 - image[i][j] will produce different results. If this is a possibility, you might want to add a check to ensure that the input image is indeed binary.

Here's an example showing the edge case of an empty image:

image3 = []
print(flipAndInvertImage(image3)) # Output: []