Cruise Ship Treasure Hunt - codepath/compsci_guides GitHub Wiki

Unit 7 Session 2 (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 20 mins
  • 🛠️ Topics: Divide and Conquer, Matrix Search

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Q: What should be returned if the treasure is not found in the matrix?
    • A: Return (-1, -1) since the treasure is not in the matrix.
  • Q: Are the room numbers unique in the matrix?
    • A: Yes, the problem assumes that all room numbers are unique.
  • Q: Is the matrix always sorted row-wise and column-wise?
    • A: Yes, both rows and columns are sorted in ascending order.
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.

2: M-atch

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:

  • Divide and Conquer: Use a divide-and-conquer approach to narrow down the search area within the matrix.
  • Greedy Search: A greedy approach can be used by starting from the top-right corner and iteratively narrowing down the search based on the value comparison.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

Plan

  1. Start from the Top-Right Corner: Begin the search from the top-right corner of the matrix.
  2. Compare Values:
    • If the current value equals the treasure, return its coordinates.
    • If the current value is greater than the treasure, move left to a smaller column.
    • If the current value is less than the treasure, move down to a larger row.
  3. Terminate: The loop terminates when the treasure is found or when the indices go out of bounds.

Greedy Search Implementation

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).

4: I-mplement

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

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Trace through your code with the input rooms = [1, 4, 7, 11], [8, 9, 10, 20], [11, 12, 17, 30], [18, 21, 23, 40](/codepath/compsci_guides/wiki/1,-4,-7,-11],-[8,-9,-10,-20],-[11,-12,-17,-30],-[18,-21,-23,-40) and treasure = 17:
    • The search should correctly identify the coordinates (2, 2) as the location of the treasure.

6: E-valuate

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.

  • Time Complexity: O(M + N) because the algorithm may traverse the entire top row and rightmost column in the worst case.
  • Space Complexity: O(1) as the space used is constant regardless of input size.