LeetCode 832 - Flipping an Image

The problem requires transforming an n x n binary matrix in two steps: first flipping it horizontally, then inverting it.

leetcodeeasyarraytwo-pointersbit-manipulationmatrixsimulation

LeetCode Problem 832

Difficulty: 🟢 Easy
Topics: Array, Two Pointers, Bit Manipulation, Matrix, Simulation

Solution

Problem Understanding

The problem requires transforming an n x n binary matrix in two steps: first flipping it horizontally, then inverting it. Horizontally flipping a row means reversing the order of elements in that row, so the first element becomes last, the second becomes second-to-last, and so on. Inverting a row means changing all 0s to 1s and all 1s to 0s. The input image is a square matrix of size n x n with elements constrained to 0 or 1, and n is guaranteed to be between 1 and 20. The output should be the matrix after applying both transformations to every row.

Important considerations include handling rows of odd or even length, which affects how flipping is implemented, and ensuring that inversion happens correctly on all elements after flipping. Edge cases could include a 1x1 matrix, a matrix where all elements are 0 or 1, or matrices that require in-place flipping to optimize space.

Approaches

The brute-force approach is straightforward: iterate over each row, reverse the row, then invert each element one by one. This is simple and works correctly because it directly implements the problem's instructions. It is acceptable given the constraints (n <= 20), but it performs two passes over each row, which could be slightly optimized.

The optimal approach combines the horizontal flip and inversion in a single pass for each row. Using two pointers, one starting at the beginning and the other at the end of the row, swap the elements and simultaneously invert them. This reduces the number of operations per row roughly by half, as you handle both transformations at the same time. If the row has an odd length, the middle element is inverted separately after the swapping loop.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(1) Reverse each row, then invert each element separately
Optimal O(n^2) O(1) Combine horizontal flip and inversion using two pointers, in-place

Algorithm Walkthrough

  1. Iterate over each row in the matrix. Each row will be processed independently.
  2. Initialize two pointers: left at the start of the row and right at the end.
  3. While left <= right, swap the elements at left and right and simultaneously invert them. Inversion can be done with 1 - value.
  4. If left == right (i.e., the row has odd length and we reached the middle), invert the middle element.
  5. Increment left and decrement right to move toward the center of the row.
  6. Continue until all rows have been processed.
  7. Return the transformed matrix.

Why it works: By swapping and inverting elements simultaneously, we ensure each element is placed in its horizontally flipped position while being inverted. Using two pointers guarantees that we handle each row efficiently in one pass, and separately inverting the middle element for odd-length rows ensures correctness.

Python Solution

from typing import List

class Solution:
    def flipAndInvertImage(self, image: List[List[int]]) -> List[List[int]]:
        for row in image:
            left, right = 0, len(row) - 1
            while left <= right:
                # Swap and invert simultaneously
                row[left], row[right] = 1 - row[right], 1 - row[left]
                left += 1
                right -= 1
        return image

The implementation iterates over each row and uses two pointers to flip and invert in-place. Swapping with simultaneous inversion ensures each element is processed exactly once, handling both even and odd-length rows efficiently.

Go Solution

func flipAndInvertImage(image [][]int) [][]int {
    for i := range image {
        row := image[i]
        left, right := 0, len(row)-1
        for left <= right {
            // Swap and invert simultaneously
            row[left], row[right] = 1-row[right], 1-row[left]
            left++
            right--
        }
    }
    return image
}

The Go implementation mirrors the Python version. It uses in-place swaps with inversion. Go requires careful handling of slices, but the logic remains the same.

Worked Examples

Example 1:

Input: [[1,1,0],[1,0,1],[0,0,0]]

Step-by-step:

Row Initial After Flip After Invert
1 [1,1,0] [0,1,1] [1,0,0]
2 [1,0,1] [1,0,1] [0,1,0]
3 [0,0,0] [0,0,0] [1,1,1]

Output: [[1,0,0],[0,1,0],[1,1,1]]

Example 2:

Input: [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]

Step-by-step:

Row Initial After Flip After Invert
1 [1,1,0,0] [0,0,1,1] [1,1,0,0]
2 [1,0,0,1] [1,0,0,1] [0,1,1,0]
3 [0,1,1,1] [1,1,1,0] [0,0,0,1]
4 [1,0,1,0] [0,1,0,1] [1,0,1,0]

Output: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]

Complexity Analysis

Measure Complexity Explanation
Time O(n^2) Each of the n rows is processed, and each row has n elements
Space O(1) The transformation is done in-place; no additional data structures are needed

The algorithm is efficient for the given constraint n <= 20, and the in-place operations save memory.

Test Cases

# Provided examples
assert Solution().flipAndInvertImage([[1,1,0],[1,0,1],[0,0,0]]) == [[1,0,0],[0,1,0],[1,1,1]]  # Example 1
assert Solution().flipAndInvertImage([[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]) == [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]  # Example 2

# Edge cases
assert Solution().flipAndInvertImage([[1]]) == [[0]]  # Single element
assert Solution().flipAndInvertImage([[0]]) == [[1]]  # Single element zero
assert Solution().flipAndInvertImage([[1,0]]) == [[1,0]]  # Two elements, different
assert Solution().flipAndInvertImage([[0,0]]) == [[1,1]]  # Two zeros
assert Solution().flipAndInvertImage([[1,1]]) == [[0,0]]  # Two ones
Test Why
Single element Tests the minimal input edge case
Two elements Ensures flipping and inverting works for even-length rows
Mixed examples Validates correctness on provided sample inputs
All zeros or all ones Checks inversion logic across uniform rows

Edge Cases

  1. Single element matrix: The smallest possible input. Without proper handling, code could attempt unnecessary swaps or fail to invert the single value. The implementation correctly handles left == right and inverts the single element.
  2. Odd-length rows: When the row length is odd, the middle element must be inverted without swapping. The two-pointer loop with left <= right ensures that the middle element is processed exactly once.
  3. Uniform rows: Rows containing all 0s or all 1s test inversion logic. The in-place inversion using 1 - value guarantees correctness regardless of uniformity, avoiding errors like attempting to invert using a conditional statement.