Minimum Effort Path to the Castle - codepath/compsci_guides GitHub Wiki

Unit 11 Session 2 Advanced (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 50 mins
  • 🛠️ Topics: Dijkstra's Algorithm, Graph Traversal

1: U-nderstand

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?
  • How is the effort calculated?
    • The effort is defined as the maximum absolute difference in heights between two consecutive locations along the path.
  • What is the goal of the problem?
    • The goal is to minimize the effort required to travel from the top-left corner to the bottom-right corner of the grid.
HAPPY CASE
Input: 
    heights = [
        [1, 2, 2],
        [3, 8, 2],
        [5, 3, 5]
    ]
Output: 
    2
Explanation:
    The path with the minimum effort of 2 can be found by traveling through cells with minimal height differences.

EDGE CASE
Input: 
    heights = [
        [1, 2, 3],
        [3, 8, 4],
        [5, 3, 5]
    ]
Output: 
    1
Explanation:
    The safest path to the castle in this scenario requires only an effort of 1, as the height differences between consecutive cells are minimal.

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 Minimum Effort Path problems, we want to consider the following approaches:

  • Dijkstra's Algorithm: This is a classic problem where you need to find the shortest path (or in this case, the path with the minimal effort) in a weighted graph.
  • Greedy Approach: At each step, we want to move to the cell with the minimum possible effort, which is exactly how Dijkstra's algorithm operates.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use Dijkstra's algorithm to traverse the grid and find the path with the minimal effort. We'll use a min-heap to always explore the cell with the smallest current effort, updating the effort required to reach neighboring cells as we go.

Steps:

  1. Initialization:

    • Define the grid size rows and cols.
    • Create a min_effort array that will store the minimum effort required to reach each cell.
    • Initialize a priority queue (min-heap) with the starting cell (top-left corner).

  2. Heap-Based Exploration:

    • While the heap is not empty:
      • Extract the cell with the minimum current effort.
      • If we've reached the bottom-right corner, return the effort.
      • Explore neighboring cells (up, down, left, right):
        • Calculate the effort to move to the neighbor.
        • If the new effort is smaller than the previously recorded effort for that neighbor, update it and push the neighbor to the heap.

  3. Termination:

    • If the loop completes and we haven't reached the bottom-right corner (which shouldn't happen), return 0.

4: I-mplement

Implement the code to solve the algorithm.

import heapq

def min_effort(heights):
    rows, cols = len(heights), len(heights[0])
    
    # Directions for up, down, left, and right movement
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    
    # min_effort array to track the minimum effort to reach each cell
    min_effort = [[float('inf')] * cols for _ in range(rows)]
    min_effort[0][0] = 0
    
    # Min-heap to perform Dijkstra's Algorithm
    heap = [(0, 0, 0)]  # (effort, row, col)
    
    while heap:
        current_effort, row, col = heapq.heappop(heap)
        
        # If we've reached the bottom-right corner, return the effort
        if row == rows - 1 and col == cols - 1:
            return current_effort
        
        # Explore all neighboring cells
        for dr, dc in directions:
            new_row, new_col = row + dr, col + dc
            if 0 <= new_row < rows and 0 <= new_col < cols:
                # Calculate the effort to move to the new cell
                new_effort = max(current_effort, abs(heights[row][col] - heights[new_row][new_col]))
                
                # If a smaller effort path is found, update and push to the heap
                if new_effort < min_effort[new_row][new_col]:
                    min_effort[new_row][new_col] = new_effort
                    heapq.heappush(heap, (new_effort, new_row, new_col))
    
    return 0  # In case no valid path is found (shouldn't happen with the given problem constraints)

5: R-eview

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

Example 1:

  • Input: heights = [ [1, 2, 2], [3, 8, 2], [5, 3, 5] ]
  • Expected Output: 2

Example 2:

  • Input: heights = [ [1, 2, 3], [3, 8, 4], [5, 3, 5] ]
  • Expected Output: 1

6: E-valuate

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

Assume m is the number of rows and n is the number of columns.

  • Time Complexity: O(m * n log (m * n)) due to Dijkstra's algorithm exploring all cells and using a heap.
  • Space Complexity: O(m * n) to store the min_effort array and the heap.