Path With Maximum Minimum Value - Leetcode Solution

Problem Statement:

Given a matrix of integers A with R rows and C columns, find the maximum score of a path starting at [0,0] and ending at [R-1,C-1].

The score of a path is the minimum value in that path. For example, the value of the path 8 → 4 → 5 → 9 is 4.

A path moves some number of times from one visited cell to any neighbouring unvisited cell in one of the 4 cardinal directions (north, east, west, south).

Solution:

Approach: The given problem can be solved using binary search and DFS. The idea is to perform a binary search over the range of values of the minimum value in the path from 0 to maximum element in the grid. For each value of minimum value, we perform a DFS from source which can lead us to the destination with minimum value mid. If we can reach the destination with minimum possible value mid, then we check the upper half values of the binary search range. Otherwise, we go to lower half values.

Algorithm:

1. Perform Binary Search. Initialize low=0, high=max_element_in_matrix.
2. In each search, a. mid=(low+high)//2. b. Start DFS from (0,0) to (R-1,C-1) checking if every visited node has a value >= mid. c. If a path from (0,0) to (R-1,C-1) exists with all values >= mid, check upper half values. d. Otherwise, check lower half values.
3. Return low which gives the maximum possible minimum in any possible path from (0,0) to (R-1,C-1).

Code:

class Solution: def maximumMinimumPath(self, A: List[List[int]]) -> int:

    def dfs(A, i, j, target, visited):
        R, C = len(A), len(A[0])
        
        #marking current cell visited
        visited.add((i,j))
        
        #if we have reached the target cell
        if i==R-1 and j==C-1:
            return True
        
        adj = [(0,1), (1,0), (-1,0), (0,-1)]
        for x, y in adj:
            #calculating the next cell cord
            jr, jc = i+x, j+y
            
            #if the next cell cords are valid and not already visited and the cell value is greater than or equal to target
            if 0<=jr<R and 0<=jc<C and (jr, jc) not in visited and A[jr][jc]>=target:
                if dfs(A, jr, jc, target, visited):
                    return True
        
        #if destination is not reached
        return False
    
    low, high = 0, max(max(A, key=lambda x: max(x))) #initializing the binary search range
    
    while low <= high:
        mid = (low+high)//2
        
        #creating the visited set and marking (0,0) cell as visited
        visited = set()
        visited.add((0,0))
        
        #calling DFS to check if we can reach the destination with all values >= mid
        if dfs(A, 0, 0, mid, visited):
            low = mid+1 #checking upper half possible values of target
        else:
            high = mid-1 #checking lower half possible values of target
    
    return low-1 #returning maximum possible minimum value in any possible path from (0,0) to (R-1,C-1)

1