Flipping an Image

Problem#

For each row of a binary matrix: reverse it horizontally, then invert it (0↔1). Return the result.

Examples#

[[1,1,0],[1,0,1],[0,0,0]] → [[1,0,0],[0,1,0],[1,1,1]].
[[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]] → [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]].

Constraints#

1 <= n <= 20.

Approach#

For each row, use two pointers l = 0, r = n-1. Swap-and-flip the values: write 1 - image[r] to slot l and 1 - image[l] to slot r. When l == r, flip in place.

Solution#

class Solution {
public:
    vector<vector<int>> flipAndInvertImage(vector<vector<int>>& image) {
        int n = image.size();
        for (auto& row : image) {
            int l = 0, r = n - 1;
            while (l < r) {
                int a = row[l] ^ 1, b = row[r] ^ 1;
                row[l] = b;
                row[r] = a;
                ++l; --r;
            }
            if (l == r) row[l] ^= 1;
        }
        return image;
    }
};

func flipAndInvertImage(image [][]int) [][]int {
    n := len(image)
    for _, row := range image {
        l, r := 0, n-1
        for l < r {
            a := row[l] ^ 1
            b := row[r] ^ 1
            row[l] = b
            row[r] = a
            l++
            r--
        }
        if l == r {
            row[l] ^= 1
        }
    }
    return image
}

from typing import List

class Solution:
    def flipAndInvertImage(self, image: List[List[int]]) -> List[List[int]]:
        n = len(image)
        for row in image:
            l, r = 0, n - 1
            while l < r:
                a = row[l] ^ 1
                b = row[r] ^ 1
                row[l] = b
                row[r] = a
                l += 1
                r -= 1
            if l == r:
                row[l] ^= 1
        return image

var flipAndInvertImage = function(image) {
    const n = image.length;
    for (const row of image) {
        let l = 0, r = n - 1;
        while (l < r) {
            const a = row[l] ^ 1;
            const b = row[r] ^ 1;
            row[l] = b;
            row[r] = a;
            l++;
            r--;
        }
        if (l === r) row[l] ^= 1;
    }
    return image;
};

class Solution {
    public int[][] flipAndInvertImage(int[][] image) {
        int n = image.length;
        for (int[] row : image) {
            int l = 0, r = n - 1;
            while (l < r) {
                int a = row[l] ^ 1;
                int b = row[r] ^ 1;
                row[l] = b;
                row[r] = a;
                l++;
                r--;
            }
            if (l == r) row[l] ^= 1;
        }
        return image;
    }
}

function flipAndInvertImage(image: number[][]): number[][] {
    const n = image.length;
    for (const row of image) {
        let l = 0, r = n - 1;
        while (l < r) {
            const a = row[l] ^ 1;
            const b = row[r] ^ 1;
            row[l] = b;
            row[r] = a;
            l++;
            r--;
        }
        if (l === r) row[l] ^= 1;
    }
    return image;
}

Editorial#

Reversing then inverting is the same as a single two-pointer pass that flips during the swap. XOR with 1 is the cleanest way to invert a 0/1 bit. The middle-element case for odd-length rows needs an explicit flip after the loop.

Complexity#

Time: O(n^2).
Space: O(1) in-place.

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#