Understand what the interviewer is asking for by using test cases and questions about the problem.
- Established a set (2-3) of test cases to verify their own solution later.
- Established a set (1-2) of edge cases to verify their solution handles complexities.
- Have fully understood the problem and have no clarifying questions.
- Have you verified any Time/Space Constraints for this problem?
O(m*n)
, m being the rows of the array and n being the columns of array. Space complexity should be O(1)
.HAPPY CASE
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]]
```markdown
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]]
EDGE CASE
Input: matrix = [[1]]
Output: [[1]]
Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.
For 2D-Array, common solution patterns include:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Let's reverse each row, then flip every 1 to 0 and 0 to 1 in-place.
1) Use the reverse function on each row
2) For each row flip each item from 0 to 1 and 0 to 1
⚠️ Common Mistakes
Implement the code to solve the algorithm.
class Solution:
def flipAndInvertImage(self, image: List[List[int]]) -> List[List[int]]:
# Use the reverse function on each row
for row in image:
row.reverse()
# For each row flip each item from 0 to 1 and 0 to 1.
for i, element in enumerate(row):
if element == 1:
row[i] = 0
else:
row[i] = 1
return image
class Solution {
public int[][] flipAndInvertImage(int[][] A) {
int row = A.length;
int col = A[0].length;
int[][] result = new int[row][col];
// Use the reverse function on each row
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
result[i][j] = A[i][col-j-1];
}
}
// For each row flip each item from 0 to 1 and 0 to 1.
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
result[i][j] = result[i][j] == 1 ? 0 : 1;
}
}
return result;
}
}
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
Assume N
represents the number of rows in 2D-array.
Assume M
represents the number of columns in 2D-array.