Problem

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].

Examples

Example 1

1
2
3
4
5
6
7
8


    
    
    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

1
2
3
4
5
6
7
8


    
    
    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.

Solution

Method 1 – Two-Pointer Row Reversal and Bitwise Inversion

Intuition

We can flip each row in place using two pointers (one from each end), and simultaneously invert the values using bitwise XOR. This is efficient and avoids extra space.

Approach

  1. For each row in the matrix:
    • Use two pointers (l and r) to swap elements from both ends.
    • While swapping, invert both elements using 1 - x or x ^ 1.
    • If the row has odd length, invert the middle element.
  2. Return the modified matrix.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    vector<vector<int>> flipAndInvertImage(vector<vector<int>>& img) {
        for (auto& row : img) {
            int l = 0, r = row.size() - 1;
            while (l <= r) {
                int tmp = row[l] ^ 1;
                row[l] = row[r] ^ 1;
                row[r] = tmp;
                l++; r--;
            }
        }
        return img;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

type Solution struct{}
func (Solution) flipAndInvertImage(img [][]int) [][]int {
    for i := range img {
        l, r := 0, len(img[i])-1
        for l <= r {
            img[i][l], img[i][r] = img[i][r]^1, img[i][l]^1
            l++
            r--
        }
    }
    return img
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int[][] flipAndInvertImage(int[][] img) {
        for (int[] row : img) {
            int l = 0, r = row.length - 1;
            while (l <= r) {
                int tmp = row[l] ^ 1;
                row[l] = row[r] ^ 1;
                row[r] = tmp;
                l++; r--;
            }
        }
        return img;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun flipAndInvertImage(img: Array<IntArray>): Array<IntArray> {
        for (row in img) {
            var l = 0
            var r = row.size - 1
            while (l <= r) {
                val tmp = row[l] xor 1
                row[l] = row[r] xor 1
                row[r] = tmp
                l++
                r--
            }
        }
        return img
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def flipAndInvertImage(self, img: list[list[int]]) -> list[list[int]]:
        for row in img:
            l, r = 0, len(row) - 1
            while l <= r:
                row[l], row[r] = row[r] ^ 1, row[l] ^ 1
                l += 1
                r -= 1
        return img
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

impl Solution {
    pub fn flip_and_invert_image(img: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let mut img = img;
        for row in img.iter_mut() {
            let n = row.len();
            for i in 0..=(n-1)/2 {
                let tmp = row[i] ^ 1;
                row[i] = row[n-1-i] ^ 1;
                row[n-1-i] = tmp;
            }
        }
        img
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
  flipAndInvertImage(img: number[][]): number[][] {
    for (let row of img) {
      let l = 0, r = row.length - 1;
      while (l <= r) {
        [row[l], row[r]] = [row[r] ^ 1, row[l] ^ 1];
        l++;
        r--;
      }
    }
    return img;
  }
}

Complexity

  • ⏰ Time complexity: O(n^2), since each element in the matrix is visited once.
  • 🧺 Space complexity: O(1), as the operation is done in place.