The trick here is to name the state correctly, then let the implementation follow. For 832. Flipping an Image, the solution in this repository is mainly a two pointers solution.
Guide
What?
Before optimizing anything, pin down what information is still useful after each move. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: two pointers, bit manipulation.
Guide
When?
Reach for this shape when a direct simulation would work logically but waste time revisiting the same information. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are op_inverse.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(N), where N is the total number of elements in A.
- Space: O(1) in additional space complexity.
Guide
C++ Solution
Your submission
The accepted solution
01/**
02Given a binary matrix A, we want to flip the image horizontally, then invert it, and return the resulting image.
03
04To 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].
05
06To 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].
07
08Example 1:
09
10Input: [[1,1,0],[1,0,1],[0,0,0]]
11Output: [[1,0,0],[0,1,0],[1,1,1]]
12Explanation: First reverse each row: [[0,1,1],[1,0,1],[0,0,0]].
13Then, invert the image: [[1,0,0],[0,1,0],[1,1,1]]
14Example 2:
15
16Input: [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]
17Output: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
18Explanation: First reverse each row: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]].
19Then invert the image: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
20Notes:
21
221 <= A.length = A[0].length <= 20
230 <= A[i][j] <= 1
24**/
25
26/**
27Approach #1: Direct [Accepted]
28Intuition and Algorithm
29
30We can do this in place. In each row, the ith value from the left is equal to the inverse of the ith value from the right.
31
32We use (C+1) / 2 (with floor division) to iterate over all indexes i in the first half of the row, including the center.
33
34//Java
35class Solution {
36 public int[][] flipAndInvertImage(int[][] A) {
37 int C = A[0].length;
38 for (int[] row: A)
39 for (int i = 0; i < (C + 1) / 2; ++i) {
40 int tmp = row[i] ^ 1;
41 row[i] = row[C - 1 - i] ^ 1;
42 row[C - 1 - i] = tmp;
43 }
44
45 return A;
46 }
47}
48
49Complexity Analysis
50
51Time Complexity: O(N), where N is the total number of elements in A.
52
53Space Complexity: O(1) in additional space complexity.
54**/
55
56//Your runtime beats 100.00 % of cpp submissions.
57class Solution {
58//the keyword 'static' fixes "invalid use of non-static member function 'int Solution::op_inverse(int)'"
59static int op_inverse (int i) { return 1-i; }
60public:
61 vector<vector<int>> flipAndInvertImage(vector<vector<int>>& A) {
62 for(int i = 0; i < A.size(); i++){
63 reverse(A[i].begin(),A[i].end());
64 transform (A[i].begin(), A[i].end(), A[i].begin(), op_inverse);
65 }
66 return A;
67 }
68};Cost