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
imagerepresenting ann x nbinary 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
0or1. - The size of the matrix
nranges from1to20.
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
- Iterate over each row in the matrix.
- For each row, use two pointers: one starting from the beginning (
left) and the other from the end (right). - Swap the values at these two pointers and invert them simultaneously.
- If
leftequalsright, it means we are at the middle element of an odd-sized row, so we simply invert this single element. - 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
1x1matrix 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.