Finding the Shallowest Point - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 25 mins
  • 🛠️ Topics: Divide and Conquer, Recursion

1: U-nderstand

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

  • Q: Can the list be empty?
    • A: The problem assumes that the list will contain at least one depth value.
  • Q: Are the depths guaranteed to be non-negative?
    • A: Yes, as per the problem statement.
HAPPY CASE
Input: depths = [5, 7, 2, 8, 3]
Output: 2
Explanation: The shallowest point is 2.

Input: depths = [12, 15, 10, 21]
Output: 10
Explanation: The shallowest point is 10.

EDGE CASE
Input: depths = [5]
Output: 5
Explanation: Only one depth value, so it is the shallowest.

Input: depths = [20, 19, 18, 17, 16, 15, 14, 13, 12, 11]
Output: 11
Explanation: The shallowest point is 11.

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 Divide and Conquer problems, we want to consider the following approaches:

  • Divide and Conquer: The problem can be divided into smaller sub-problems (smaller arrays) where we find the minimum depth in each half of the array recursively.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a divide-and-conquer approach by recursively splitting the list into two halves and finding the minimum in each half until we reach the base case where the list contains a single element.

1) Define a helper function that takes a subarray defined by two indices `left` and `right`.
2) If the subarray has only one element, return that element as the minimum.
3) Otherwise, find the midpoint of the current subarray.
4) Recursively find the minimum value in the left and right subarrays.
5) Return the smaller of the two values found in the left and right subarrays.
6) The main function will call this helper function on the entire array and return the result.

⚠️ Common Mistakes

  • Not correctly handling the base case when the subarray has only one element.
  • Incorrectly managing the indices while splitting the array.

4: I-mplement

Implement the code to solve the algorithm.

def find_shallowest_point(depths):
    def find_min_in_subarray(left, right):
        # Base case: if the subarray contains one element
        if left == right:
            return depths[left]
        
        # Find the midpoint of the current subarray
        mid = left + (right + left) // 2
        
        # Recursively find the minimum in the left and right subarrays
        left_min = find_min_in_subarray(left, mid)
        right_min = find_min_in_subarray(mid + 1, right)
        
        # Return the smaller of the two minimums
        return min(left_min, right_min)
    
    # Call the helper function on the entire array
    return find_min_in_subarray(0, len(depths) - 1)

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 [5, 7, 2, 8, 3]:
    • The function should split the array and correctly identify 2 as the minimum value.

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N represents the length of the depths array.

  • Time Complexity: O(N) because each element is visited once as the array is split.
  • Space Complexity: O(log N) due to the recursive call stack, as the array is split in half with each recursive call.