Menu

Subscribe

Find the maximum min path

on dynamic programming, algorithms, unlisted

Problem

Given a matrix of integers, there are many paths to take from the top left to the bottom right. For each path, the smallest number in the path is the min of the path. Of all the min paths, find the maximum min path.

Examples:

[8, 4, 7]
[6, 5, 9]

There are 3 paths that can be taken from (0, 0) to (2, 1)  
8-4-7-9 min: 4  
8-4-5-9 min: 4  
8-6-5-9 min: 5 

The greatest min path is 5.

Input

  • M - a 2D matrix composed of integers

Approach

The brute force approach is to recursively traverse down and right from a block in the matrix, and record the minimum as you go along. When you hit the bottom-right of the matrix, you can then update the result with the minimum only if the result is smaller than this minimum.

Solution

def find_max_min_path(M):  
    n = len(M)
    m = len(M[0])
    result = -float('inf')

    def _find_max_min(i, j, min_so_far):
        if i >= m or j >= n:
            return

        curr_min = min(M[j][i], min_so_far)
        nonlocal result

        if i == m-1 and j == n-1:
            result = max(result, curr_min)
            return

        _find_max_min(i+1, j, curr_min)
        _find_max_min(i, j+1, curr_min)

    _find_max_min(0, 0, float('inf'))

    return result

Solution (Optimized)

An optimization is to use dynamic programming, as the previous solution will repeatedly visit blocks that were visited before.

The basic intuition for the dynamic programming approach is that we create another 2D matrix dp (same size as the original input) and as we walk through the matrix M, we cache the results into dp.

Each block in dp has the maximum min path value.
\(dp[j][i]\) is the minimum of two things:

  • The maximum of the entry right before it: (\(i-1\) or \(j-1\))
  • The current value at \(M[j][i]\)
def find_max_min_dp(M):  
    n = len(M)
    m = len(M[0])

    dp = [[0] * m for _ in range(n)]
    dp[0][0] = M[0][0]

    for i in range(1, m):
        dp[0][i] = min(M[0][i], dp[0][i-1])

    for j in range(1, n):
        dp[j][0] = min(M[j][0], dp[j-1][0])

    for i in range(1, m):
        for j in range(1, n):
            dp[j][i] = min(max(dp[j-1][i], dp[j][i-1]), M[j][i])

    return dp[n-1][m-1]