Leetcode problem 92 - Flipping an Image

Given an n x n binary matrix image, flip the image horizontally, then invert it, and return the resulting image.

To flip an image horizontally means that each row of the image is reversed.

For example, flipping [1,1,0] horizontally results in [0,1,1]. To invert an image means that each 0 is replaced by 1, and each 1 is replaced by 0.

For example, inverting [0,1,1] results in [1,0,0].

Example 1:

Input: image = [[1,1,0],[1,0,1],[0,0,0]] Output: [[1,0,0],[0,1,0],[1,1,1]] Explanation: First reverse each row: [[0,1,1],[1,0,1],[0,0,0]]. Then, invert the image: [[1,0,0],[0,1,0],[1,1,1]] Example 2:

Input: image = [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]] Output: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]] Explanation: First reverse each row: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]]. Then invert the image: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]

Constraints:

n == image.length n == image[i].length 1 <= n <= 20 images[i][j] is either 0 or 1.

/**
 * @param {number[][]} image
 * @return {number[][]}
 */
var flipAndInvertImage = function (image) {
  // Iterate through each row in the image array
  for (const img of image) {
    let left = 0; // Initialize left pointer for the current row
    let right = img.length - 1; // Initialize right pointer for the current row

    // Process each pair of elements symmetrically from the outer edges towards the center
    while (left <= right) {
      // Swap and invert the values at the left and right positions
      let temp = img[left] ? 0 : 1; // Invert the value (0 to 1, 1 to 0)
      img[left] = img[right] ? 0 : 1; // Invert the value and assign to left position
      img[right] = temp; // Assign the inverted value to the right position

      // Move the pointers towards the center
      left++;
      right--;
    }
  }

  // Return the modified image array
  return image;
};

Time Complexity: The time complexity of this algorithm is O(n * m), where n is the number of rows in the image, and m is the number of elements in each row. The reason is that the algorithm iterates through each element of the image array once.

Space Complexity: The space complexity is O(1), as the algorithm only uses a constant amount of extra space for variables like left, right, and temp. The input image is modified in place, and no additional data structures are used that scale with the input size.