DSA AnimatorREVISION VIDEOS
← Back to problems
New

Flipping an Image — LeetCode 832 video explanation

You get a square image of 0s and 1s. First flip each row horizontally, which reverses it. Then invert it: every 0 becomes 1, and every 1 becomes 0.

Loading videos…

DSA Animator › DSA Revision › Arrays › Flipping an Image

Key moments in the Flipping an Image video

0:04Problem0:14Example0:27Brute force0:35Key idea0:45Dry run1:11Code1:28Takeaway

What you will learn

Remember: reverse means two pointers swapping from both ends. Inverting a bit is x exclusive or 1, and it can be done during the swap. The video solves Flipping an Image (LeetCode 832, Easy) with the 2D Array pattern from the Arrays topic, and you can replay every step in the interactive Flipping an Image animation.

Flipping an Image video transcript

Problem

You get a square image of 0s and 1s. First flip each row horizontally, which reverses it. Then invert it: every 0 becomes 1, and every 1 becomes 0.

Example

For rows 1 1 0, 1 0 1 and 0 0 0, reversing gives 0 1 1, 1 0 1 and 0 0 0. Inverting then gives 1 0 0, 0 1 0 and 1 1 1.

Brute force

You could reverse each row in one pass, then invert it in another. Both steps can happen together, in a single pass from both ends.

Key idea

Swap the values at the left and right ends of the row, and invert both while you swap. Move the two ends inward until they meet. If they meet on the middle cell, just invert that one.

Dry run

Row 0 is 1 1 0: the ends are 1 and 0, which swap and invert into 1 and 0, and the middle 1 inverts to 0. Row 0 becomes 1 0 0. Row 1 is 1 0 1: the ends swap and invert into 0 and 0, and the middle 0 becomes 1, so 0 1 0. Row 2 is 0 0 0, which becomes 1 1 1. The answer is 1 0 0, 0 1 0 and 1 1 1.

Code

In code, loop over the rows. Keep two pointers at both ends of the row. Swap the two values, and flip each one with an exclusive or with 1. When the pointers meet in the middle, flip that single value. Every cell is touched once, so it's O of n squared time, and O of 1 extra space.

Takeaway

Remember: reverse means two pointers swapping from both ends. Inverting a bit is x exclusive or 1, and it can be done during the swap.

More Arrays revision videos

← All 185 DSA revision videos