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 matrix and N being the columns of matrix. Space complexity should be O(M*N)
too.HAPPY CASE
Input: matrix = [[3,7,8],[9,11,13],[15,16,17]]
Output: [15]
Explanation: 15 is the only lucky number since it is the minimum in its row and the maximum in its column.
nput: matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]]
Output: [12]
Explanation: 12 is the only lucky number since it is the minimum in its row and the maximum in its column.
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: Create a set of minimum number in each row and a set of maximum number in each column. If a number is in both set, then it is both the minimum number in the row and maximum number in the column.
1) Create variables to hold minimum row numbers and maximum column numbers.
2) Search each row in matrix for minimum number and create minimum row numbers set
3) Search each column in matrix for maximum number and create maximum column numbers set
a) Transpose the matrix using zip(*matrix) to create columns
- For more information see https://github.com/codepath/compsci_guides/wiki/Transpose-Matrix
b) Store maximum number per column in set
4) Return a list of numbers that is in both sets.
⚠️ Common Mistakes
Implement the code to solve the algorithm.
class Solution:
def luckyNumbers (self, matrix: List[List[int]]) -> List[int]:
# Create variables to hold minimum row numbers and maximum column numbers
minRow, maxCol = set(), set()
# Search each row in matrix for minimum number and create minimum row numbers set
for row in matrix:
minRow.add(min(row))
# Search each column in matrix for maximum number and create maximum column numbers set
# Transpose the matrix using zip(*matrix) to create columns
for col in zip(*matrix):
# Store maximum number per column in set
maxCol.add(max(col))
# Return a list of numbers that is in both sets
return list(minRow & maxCol)
class Solution {
public List<Integer> luckyNumbers (int[][] matrix) {
List<Integer> result = new ArrayList<Integer>();
// Search each row in matrix for minimum number and create minimum row numbers
for (int row = 0; row < matrix.length; row++) {
int minCol = minColInRow(matrix, row);
int value = matrix[row][minCol];
// Search each column in matrix for maximum number and create maximum column numbers
if (checkIfMaxInCol(matrix, minCol, value)) {
// Store maximum number per column
result.add(value);
}
}
// Return a list of numbers that is in both sets
return result;
}
private int minColInRow(int[][] matrix, int row) {
int minIndex = 0, min = matrix[row][minIndex];
for (int col = 1; col < matrix[row].length; col++) {
if (matrix[row][col] < min) {
min = matrix[row][col];
minIndex = col;
}
}
return minIndex;
}
private boolean checkIfMaxInCol(int[][] matrix, int col, int value) {
for (int row = 0; row < matrix.length; row++) {
if (matrix[row][col] > value) return false;
}
return true;
}
}
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.
O(N * M)
we need to view each item in the 2D-Array to get the minimum number in row and maximum number in column. O(N * M)
, because we need space to hold the results. Results may contain all items in 2D-Array.