Domain 1EasyCORE

Flipping an Image

The problem requires us to manipulate an `n x n` binary matrix by performing two operations on it: flipping each row horizontally and then inverting the values in the matrix. The input is a 2D list (matrix) where each element is either `0` or `1`. The output should be the modified matrix after applying both operations.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array

832. Flipping an Image

Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 1
Acceptance rate: 78.3%


Problem Breakdown

The problem requires us to manipulate an n x n binary matrix by performing two operations on it: flipping each row horizontally and then inverting the values in the matrix. The input is a 2D list (matrix) where each element is either 0 or 1. The output should be the modified matrix after applying both operations.

Inputs:

  • A 2D list image representing an n x n binary matrix.

Outputs:

  • A 2D list representing the modified matrix after flipping and inverting each row.

Implicit Constraints:

  • The matrix is square (n x n).
  • Each element in the matrix is either 0 or 1.
  • The size of the matrix n ranges from 1 to 20.

Intuition

A brute-force approach would involve iterating over each row, reversing it, and then inverting each element. This approach has a time complexity of O(n^2) because we need to process each element twice (once for flipping and once for inverting). However, we can optimize this by combining the two operations into a single pass.

The key insight is that flipping a row and then inverting it can be achieved by swapping elements from the start and end of the row towards the center. During this swap, we also invert the values simultaneously. This reduces the number of operations needed and maintains the time complexity at O(n^2) but with fewer iterations.

Approach

  1. Iterate over each row in the matrix.
  2. For each row, use two pointers: one starting from the beginning (left) and the other from the end (right).
  3. Swap the values at these two pointers and invert them simultaneously.
  4. If left equals right, it means we are at the middle element of an odd-sized row, so we simply invert this single element.
  5. Continue this process until all rows have been processed.

Complexity Analysis

  • Time Complexity: O(n^2), where n is the number of rows (or columns) in the matrix. We iterate over each element exactly once.
  • Space Complexity: O(1), as we are modifying the matrix in place and not using any additional data structures that scale with input size.

Solution

def flipAndInvertImage(image):
    n = len(image)
    
    for row in image:
        left, right = 0, n - 1
        while left <= right:
            # Swap and invert the elements at left and right pointers
            row[left], row[right] = 1 - row[right], 1 - row[left]
            if left != right:
                # Invert the middle element if it exists (for odd-sized rows)
                row[(left + right) // 2] = 1 - row[(left + right) // 2]
            left += 1
            right -= 1
    
    return image

Edge Cases Handled

  • Single-element matrix: The code correctly handles a 1x1 matrix by inverting the single element.
  • Even-sized rows: The two-pointer approach ensures that all elements are processed correctly for even-sized rows.
  • Odd-sized rows: The middle element is handled separately to ensure it is inverted correctly.

The solution provided is correct, efficient, and clear. It adheres to the problem constraints and handles all edge cases appropriately.