algoadvance

Leetcode 832. Flipping an Image

Problem Statement

The problem requires us to flip an image horizontally and then invert it.

Flipping horizontally means that each row of the image is reversed. For example, if the row is [1, 0, 1], after flipping, it will be [1, 0, 1].

Inverting means that each 0 is replaced by 1 and each 1 is replaced by 0. Continuing with the previous example, after inverting, [1, 0, 1] becomes [0, 1, 0].

Given an n x n binary matrix image, we need to return the resulting matrix after performing both operations.

Example:

Input: image = [[1,1,0],[1,0,1],[0,0,0]]
Output: [[1,0,0],[0,1,0],[1,1,1]]

Clarifying Questions

1. Will the input always be a square matrix (n x n)?
   • The problem only specifies an n x n matrix, so we will assume it is true unless specified otherwise.
2. Can we modify the input matrix in place?
   • Unless otherwise specified, we can assume either in-place mutation or creating a new matrix is acceptable.

Strategy

1. Flipping the Image Horizontally:
   • For each row in the matrix, reverse the elements.
2. Inverting the Image:
   • After flipping the rows, invert each element. Inverting is straightforward, as we can subtract the current element from 1.

Code

public class Solution {
    public int[][] flipAndInvertImage(int[][] image) {
        for (int[] row : image) {
            int length = row.length;
            // Flip the row by swapping elements from both ends up to the middle
            for (int i = 0; i < (length + 1) / 2; i++) {
                // Swap and invert the values
                int temp = row[i] ^ 1; // Invert while saving
                row[i] = row[length - 1 - i] ^ 1; // Invert while assigning
                row[length - 1 - i] = temp;
            }
        }
        return image;
    }
}

Time Complexity

• We traverse each element in the matrix exactly once to flip it and invert it.
• Let n be the number of rows and each row also has n columns.
• Time Complexity: O(n^2) because we are dealing with each element once.

Explanation

• Flipping: The inner loop swaps elements from either end of the row, effectively reversing it.
• Inverting: During the swap, the elements are also inverted by using the XOR operation with 1 (^ 1). This works because 1^1 = 0 and 0^1 = 1.
• This two-step process (flip and invert) is combined into a single loop to increase efficiency.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?