We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Flipping an Image

Number: 861

Difficulty: Easy

Paid? No

Companies: Google, IBM, Amazon

Problem Description

Given an n x n binary matrix image, flip the image horizontally (i.e., reverse each row) and then invert it by changing each 0 to 1 and each 1 to 0.

Key Insights

  • Each row is processed independently.
  • Flipping horizontally involves reversing the elements in a row.
  • Inverting each bit can be efficiently done using XOR with 1.
  • A two-pointer approach can combine both flipping and inverting in a single pass.

Space and Time Complexity

Time Complexity: O(n²) because we process each element in the n x n matrix.
Space Complexity: O(1) since the operations are performed in-place with no extra space usage.

Solution

We use a two-pointer approach to simultaneously flip and invert each row of the image. For each row, initialize two pointers (left and right). As you swap the elements at these pointers, invert them with an XOR operation. This handles even and odd sized rows in one pass, ensuring that the middle element for odd-length rows is also inverted properly.

Code Solutions

# Python solution for flipping and inverting an image.
def flipAndInvertImage(image):
    n = len(image)  # size of each row
    for row in image:
        left, right = 0, n - 1
        # Use two-pointer technique to process the row in one pass.
        while left <= right:
            if left == right:
                # Invert the middle element by XOR-ing with 1.
                row[left] ^= 1
            else:
                # Swap and invert the left and right elements.
                row[left], row[right] = row[right] ^ 1, row[left] ^ 1
            left += 1
            right -= 1
    return image

# Example Test
if __name__ == "__main__":
    test_image = [[1,1,0],[1,0,1],[0,0,0]]
    print("Output:", flipAndInvertImage(test_image))
← Back to All Questions