algoadvance

Leetcode 832. Flipping an Image

Problem Statement

The problem is to flip an image horizontally, and then invert it. To flip an image horizontally means that each row of the image is reversed. For example, given the row [1, 0, 1], flipping horizontally results in [1, 0, 1]. To invert an image means that each 0 is replaced by 1, and each 1 is replaced by 0. For example, inverting [1, 0, 1] results in [0, 1, 0].

Given a binary matrix image, you need to return the resulting image after flipping it horizontally and inverting it.

Clarifying Questions

1. Input Constraints:
   • What is the range of the dimensions of the input matrix?
   • Are there any assumptions on the input matrix, such as always being binary (i.e., containing only 0s and 1s)?
2. Edge Cases:
   • How should the function handle an empty matrix?
   • Should the function handle non-square matrices?

Code

#include <vector>
#include <algorithm>

class Solution {
public:
    std::vector<std::vector<int>> flipAndInvertImage(std::vector<std::vector<int>>& image) {
        int n = image.size();
        // Process each row
        for(int i = 0; i < n; ++i) {
            // Flip the row horizontally and invert it in one pass
            int left = 0, right = image[i].size() - 1;
            while (left <= right) {
                // Swap and invert elements at left and right indices
                if (image[i][left] == image[i][right]) {
                    image[i][left] = 1 - image[i][left];
                    image[i][right] = image[i][left];
                }
                ++left;
                --right;
            }
        }
        return image;
    }
};

Strategy

1. Flip Horizontally and Invert Simultaneously:
   • Use a two-pointer approach where one pointer starts at the beginning of the row (left), and the other starts at the end of the row (right).
   • Swap the elements at left and right while inverting them simultaneously, i.e., change 0 to 1 and 1 to 0.
   • Move the left pointer to the right and the right pointer to the left until they cross each other.
2. Final Processing:
   • Repeat the above process for each row in the matrix.

Time Complexity

• Time Complexity: O(n * m)
  • Where n is the number of rows and m is the number of columns in the input matrix.
  • Each element is processed exactly once, and there are n*m elements in total.
• Space Complexity: O(1)
  • We only use a constant amount of extra space, as the operations are performed in place on the input matrix.

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?