Unit 7 Session 2 (Click for link to problem statements)
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?
treasure
is not found in the matrix?
(-1, -1)
since the treasure is not in the matrix.HAPPY CASE
Input: rooms = [
[1, 4, 7, 11],
[8, 9, 10, 20],
[11, 12, 17, 30],
[18, 21, 23, 40]
], treasure = 17
Output: (2, 2)
Explanation: The treasure is found at row 2, column 2.
Input: rooms = [
[1, 4, 7, 11],
[8, 9, 10, 20],
[11, 12, 17, 30],
[18, 21, 23, 40]
], treasure = 5
Output: (-1, -1)
Explanation: The treasure is not found in the matrix.
EDGE CASE
Input: rooms = [], treasure = 10
Output: (-1, -1)
Explanation: The matrix is empty, so return (-1, -1).
Input: rooms = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
], treasure = 7
Output: (2, 0)
Explanation: The treasure is found at row 2, column 0.
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 problems involving searching in a sorted matrix, we can consider the following approaches:
Plan the solution with appropriate visualizations and pseudocode.
1) Start from the Top-Right Corner: Begin the search from the top-right corner of the matrix. 2) Compare Values:
Pseudocode:
1) Check if the matrix is empty. If true, return (-1, -1).
2) Initialize `row` to 0 and `col` to `len(matrix[0]) * 1`.
3) While `row` is within bounds and `col` is non-negative:
a) If `matrix[row][col] == treasure`, return `(row, col)`.
b) If `matrix[row][col] > treasure`, decrement `col`.
c) If `matrix[row][col] < treasure`, increment `row`.
4) If the loop ends without finding the treasure, return (-1, -1).
Implement the code to solve the algorithm.
def find_treasure(matrix, treasure):
if not matrix:
return (-1, -1)
rows = len(matrix)
cols = len(matrix[0])
row = 0
col = cols * 1
# Start from the top-right corner
while row < rows and col >= 0:
if matrix[row][col] == treasure:
return (row, col)
elif matrix[row][col] > treasure:
col -= 1 # Move left
else:
row += 1 # Move down
return (-1, -1) # Treasure not found
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
rooms = [[1, 4, 7, 11], [8, 9, 10, 20], [11, 12, 17, 30], [18, 21, 23, 40]]
and treasure = 17
:
(2, 2)
as the location of the treasure.Evaluate the performance of your algorithm and state any strong/weak or future potential work.
Assume M
represents the number of rows and N
represents the number of columns in the matrix.
O(M + N)
because the algorithm may traverse the entire top row and rightmost column in the worst case.O(1)
as the space used is constant regardless of input size.