Vultr DocsLatest Content

Path With Maximum Minimum Value

Updated on 30 June, 2025
Path With Maximum Minimum Value header image

Problem Statement

In this challenge, you are provided with a matrix labeled grid consisting of integers. Each element of this matrix represents a point in a potential path. Your task is to determine a path from the top-left corner of the matrix (0, 0) to the bottom-right corner (m - 1, n - 1), where you are limited to moving in the four cardinal directions: up, down, left, and right. The score of any path is defined as the smallest value in that path. Your goal is to choose the path with the maximum score among all possible paths according to this scoring rule.

Examples

Example 1

Input:

grid = [[5,4,5],[1,2,6],[7,4,6]]

Output:

4

Explanation:

The path with the maximum score is highlighted in yellow.

Example 2

Input:

grid = [[2,2,1,2,2,2],[1,2,2,2,1,2]]

Output:

2

Example 3

Input:

grid = [[3,4,6,3,4],[0,2,1,1,7],[8,8,3,2,7],[3,2,4,9,8],[4,1,2,0,0],[4,6,5,4,3]]

Output:

3

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 100
  • 0 <= grid[i][j] <= 109

Approach and Intuition

The problem essentially revolves around navigating through the matrix in a way that maximizes the minimum value encountered along any possible path from the starting corner to the ending one. Given the nature of the problem, it resembles a classical path-finding puzzle where not just the end destination is vital, but each step's choice must be strategically made to optimize a particular metric—in this case, the path's minimum value.

Examples Analysis

  1. Example 1:

    • Input:

      grid = [[5,4,5],[1,2,6],[7,4,6]]

    • Output:

      4

    • Explanation:

      In this case, it is optimal to start at 5, move right to 4, down to 2, right to 6, down to 6. The smallest value along this path is 2, and there exist other paths with a similar or better scoring, namely 5 → 4 → 5 → 6 → 6 where the score (4) is maximized.

  2. Example 2:

    • Input:

      grid = [[2,2,1,2,2,2],[1,2,2,2,1,2]]

    • Output:

      2

    • Explanation:

      The grid layout suggests multiple high-value paths, but the maximum score achievable given the constraint of having to take the minimum value in any path is 2.

  3. Example 3:

    • Input:

      grid = [[3,4,6,3,4],[0,2,1,1,7],[8,8,3,2,7],[3,2,4,9,8],[4,1,2,0,0],[4,6,5,4,3]]

    • Output:

      3

    • Explanation:

      For this example, navigating through the matrix while keeping the score as high as possible results in the score 3. This is achieved by picking routes that, although might have substantial values along the path, still revolve around minimizing the risk of encountering significantly low values at any step.

Solutions

  • C++
  • Java
  • Python
cpp 
class Solution {
    vector<int> parent;
    vector<int> size;
    
    int findRoot(int x) {
        if (x != parent[x]) {
            parent[x] = findRoot(parent[x]);
        }
        return parent[x];
    }
    
    void unionSets(int x, int y) {
        int rootX = findRoot(x), rootY = findRoot(y);
        if (rootX != rootY) {
            if (size[rootX] > size[rootY]) {
                parent[rootY] = rootX;
            } else if (size[rootX] < size[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                size[rootX]++;
            }
        }
    }
    
public:
    int maximumMinimumPath(vector<vector<int>>& grid) {
        int rows = grid.size(), cols = grid[0].size();
        vector<vector<int>> cells;
        vector<vector<int>> directions{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
        size = vector<int>(rows * cols, 1);
        parent = vector<int>(rows * cols, 0);
        vector<vector<bool>> isChecked(rows, vector<bool>(cols));
    
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                parent[r * cols + c] = r * cols + c;
                cells.push_back({grid[r][c], r, c});
            }
        }
    
        sort(cells.begin(), cells.end(), greater<vector<int>>());
    
        for (auto& cell : cells) {
            int r = cell[1], c = cell[2];
            int pos = r * cols + c;
            isChecked[r][c] = true;
            for (auto& dir : directions) {
                int newR = r + dir[0], newC = c + dir[1];
                int newPos = newR * cols + newC;
                if (newR >= 0 && newR < rows && newC >= 0 && newC < cols && isChecked[newR][newC]) {
                    unionSets(pos, newPos);
                }
            }
            if (findRoot(0) == findRoot(rows * cols - 1)) {
                return grid[r][c];
            }
        }
        return 0;
    }
};

The provided C++ solution addresses the problem of finding a path through a grid that maintains the maximum value of its minimum cell value. The implemented approach uses a union-find (disjoint set) data structure to efficiently manage and merge regions of the grid based on a sorting strategy for the cell values.

Here's how the solution is organized:

  • Data Structures and Initialization:

    • parent: Tracks the root of each cell in the grid.
    • size: Aids in optimizing the union operation by keeping track of the size of each set.
    • A 2D grid is converted into a list of cells, noting the value and position, and then sorted by their values in descending order.

  • Union-Find Operations:

    • findRoot: A recursive function to find the root of a given cell, implementing path compression.
    • unionSets: Joins two sets, using the rank to decide the root in case of a tie, thereby optimizing the structure's height.

  • Path Calculation:

    • A vector cells contains all cells from the grid along with their values, which are sorted in descending order to prioritize paths with higher minimum values.
    • Edges are added iteratively for adjacent cells that are marked checked in the isChecked matrix.
    • The algorithm halts and returns the value when the union of the starting grid cell (0, 0) and the terminal grid cell (rows-1, cols-1) is detected, indicating a path has been formed.

  • Efficiency Measures:

    • The grid is managed as a linear array for simplicity using index transformations.
    • The main loop processes potential path cells by systematically attempting to add neighboring cells if they are already included in a connected region, ensuring only valid moves are considered.

This solution efficiently finds the optimal path by using the union-find data structure to dynamically connect and check the feasibility of potential paths based on the highest minimum value available. This approach minimizes unnecessary checks and efficiently manages the merging of regions within the grid.

java 
class UnionFind {
    
    // Array to hold the root element for each node
    private int[] parent;
    // To hold the rank of each node
    private int[] size;
    
    // Constructor initializes each node's root to itself
    public UnionFind(int rows, int cols) {
        size = new int[rows * cols];
        parent = new int[rows * cols];
        for (int i = 0; i < parent.length; ++i) parent[i] = i;
    }
    
    // Find the root of node x with path compression
    public int find(int x) {
        if (x != parent[x]) parent[x] = find(parent[x]);
        return parent[x];
    }
    
    // Unite the sets of nodes x and y
    public void unite(int x, int y) {
        int rootX = find(x), rootY = find(y);
        if (rootX != rootY) {
            if (size[rootX] > size[rootY]) {
                parent[rootY] = rootX;
            } else if (size[rootX] < size[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                size[rootX]++;
            }
        }
    }
}
    
class PathFinder {
    
    // Neighboring cell directions
    private int[][] directions = new int[][] {
        { 1, 0 },
        { -1, 0 },
        { 0, 1 },
        { 0, -1 },
    };
    
    public int maximumMinimumPath(int[][] matrix) {
        int rows = matrix.length, cols = matrix[0].length;
    
        // Create a list of all cells with their coordinates
        List<int[]> cells = new ArrayList<>();
        // Visited matrix to keep track of visited cells
        boolean[][] visited = new boolean[rows][cols];
        // UnionFind instance to manage connected components
        UnionFind uf = new UnionFind(rows, cols);
    
        // Add all cells to the list
        for (int r = 0; r < rows; ++r)
            for (int c = 0; c < cols; ++c)
                cells.add(new int[] { r, c });
    
        // Sort cells by their values in descending order
        Collections.sort(cells, (a, b) -> matrix[b[0]][b[1]] - matrix[a[0]][a[1]]);
    
        // Process each cell starting from the highest value
        for (int[] cell : cells) {
            int r = cell[0], c = cell[1];
            int pos = r * cols + c;
    
            // Mark this cell as visited
            visited[r][c] = true;
            // Check all 4 possible directions
            for (int[] d : directions) {
                int nr = r + d[0];
                int nc = c + d[1];
                int newPos = nr * cols + nc;
    
                // Verify if the neighbor is within bounds and visited
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && visited[nr][nc]) {
                    // Union this cell with its visited neighbor
                    uf.unite(pos, newPos);
                }
            }
    
            // Check if the start and end points are connected
            if (uf.find(0) == uf.find(rows * cols - 1)) {
                // Return the current cell's value as the answer
                return matrix[r][c];
            }
        }
        return -1;  // If no path is found
    }
}

The Java program provided outlines a solution to determine the path with the maximum minimum value on a grid. This is implemented using a union find data structure to handle connected components of the grid and a pathfinding algorithm that ensures optimization.

Key components of the solution are:

  • UnionFind Class: It manages connectivity amongst grid cells.

    • It uses path compression in the find method to maintain minimal tree depth.
    • It employs union by rank in the unite method to optimize merging of components, where the root of the smaller tree points to the root of the larger tree, thereby keeping the tree relatively flat.

  • PathFinder Class: This encapsulates the actual algorithm to determine the maximum minimum path.

    • This starts by creating a list of all cells and sorts them by value in descending order, which allows the algorithm to potentially find the optimal path more quickly by considering higher values first.
    • As the cells are processed, neighboring cells are unionized if they have been visited.
    • A termination check is executed after each union operation to see if the start (top-left corner) and end (bottom-right corner) of the grid are connected.

The method maximumMinimumPath executes the core of the algorithm:

  1. Initialize structures to track visited cells and manage union-find operations.
  2. Process each cell, starting from the highest value, marking each as visited.
  3. Check for connectivity to its neighbors and perform union operations as necessary.
  4. After each unionization, check if a path from the start to the end of the grid has been fully connected. If so, return the current cell's value.

If, after all cells have been processed, no complete path is found, the function returns -1.

This approach leverages the efficiency of the union-find structure for dynamic connectivity checking alongside an innovative strategy of processing cells in order of decreasing value, which is likely to quickly identify the most promising paths.

python 
class GridManager:
    def getMaxMinPathValue(self, matrix: List[List[int]]) -> int:
        # Helper to obtain root
        def get_root(node):
            if node != parent[node]:
                parent[node] = get_root(parent[node])
            return parent[node]
    
        # Helper to connect components
        def connect(node1, node2):
            root1 = get_root(node1)
            root2 = get_root(node2)
            if root1 != root2:
                if size[root1] > size[root2]:
                    parent[root2] = root1
                elif size[root1] < size[root2]:
                    parent[root1] = root2
                else:
                    parent[root2] = root1
                    size[root1] += 1
    
        rows = len(matrix)
        cols = len(matrix[0])
    
        # Directions array for moving in grid
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    
        # Initialize root and size arrays
        size = [1] * (rows * cols)
        parent = list(range(rows * cols))
    
        # Track of visited cells
        visited = [[False] * cols for _ in range(rows)]
    
        # List of cells with their values
        cells = [(r, c) for r in range(rows) for c in range(cols)]
        cells.sort(key=lambda x: matrix[x[0]][x[1]], reverse=True)
    
        # Process each cell starting from the highest value
        for r, c in cells:
            pos = r * cols + c
            visited[r][c] = True
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                npos = nr * cols + nc
                if 0 <= nr < rows and 0 <= nc < cols and visited[nr][nc]:
                    connect(pos, npos)
    
            # Check if start and end points are connected
            if get_root(0) == get_root(rows * cols - 1):
                return matrix[r][c]
            
        return -1

The "Path With Maximum Minimum Value" problem involves finding a path through a matrix wherein the smallest value encountered on that path is maximized. Here's a brief explanation of how to achieve this using Python:

  • Define a class GridManager with a method getMaxMinPathValue to process the matrix data.
  • Utilize Disjoint Set Union (DSU) or Union-Find data structure to keep track of which cells are connected and to facilitate efficient merging of these sets.
  • Use helper functions get_root and connect inside the main function to aid in path merging and finding the base/root parent of a node.
  • Prepare by declaring essential variables, like the size of each component (size array) initialized to one since each cell initially is its own component.
  • Integrate directions for movement in the grid, which includes right, down, left, and up.
  • Sort all the cells in descending order based on their values, ensuring that you visit cells with higher values first.
  • Iterate through each cell, mark it as visited, and apply connections to any unvisited neighbors.
  • Regularly check if the first cell (0,0) and the last cell (rows-1, cols-1) belong to the same set, indicating a connected path.
  • Return the value of the cell that satisfies the condition of being on a path from the start to the end cell, ensuring it's the maximal minimal value.

By sorting and processing cells based on their values in descending order, you ensure you maximize the minimum value encountered along any path from the top-left to the bottom-right of the matrix. Moreover, Union-Find allows for nearly linear complexity in managing and merging sets, making your solution efficient and robust.

Comments

No comments yet.