Coding

Minimize Maximum Value in Grid

Asked at

Goldman Sachs

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

An integer matrix grid of m x n unique positive numbers is presented to you.

Every integer in the matrix must be changed to a positive integer that satisfies the following requirements:

Following the replacements, the relative order of each pair of elements in the same row or column should remain unchanged.
Following the substitutions, the maximum number in the matrix should be as low as feasible.

The relative order stays the same if for all pairs of elements in the original matrix such that grid[r1][c1] > grid[r2][c2] where either r1 == r2 or c1 == c2, then it must be true that grid[r1][c1] > grid[r2][c2] after the replacements.

For example, if grid = [[2, 4, 5], [7, 3, 9]] then a good replacement could be either grid = [[1, 2, 3], [2, 1, 4]] or grid = [[1, 2, 3], [3, 1, 4]].

Return the resulting matrix. If there are multiple answers, return any of them.

Input : grid = [ [1, 2, 3], [4, 5, 6] ] Output : [ [1, 2, 3], [2, 3, 4] ] **Explanation : **The below diagram shows a valid replacement.

The maximum number in the matrix is 4. It can be shown that no smaller value can be obtained.

Input : grid = [ [10, 12] ] Output : [ [1, 2] ] Explanation : The below diagram shows a valid replacement. The maximum number in the matrix is 4. It can be shown that no smaller value can be obtained.

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

m == grid.length
n == grid[i].length
1 <= m, n <= 1000
1 <= m * n <= 105
1 <= grid[i][j] <= 109
grid consists of distinct integers.

cpp

class Solution {
public:
    vector<vector<int>> minScore(vector<vector<int>> grid) {
        //your code goes here
    }
};

java

class Solution {
    public int[][] minScore(int[][] grid) {
        //your code goes here
    }
}

python

class Solution:
    def minScore(self, grid):
        #your code goes here

javascript

class Solution {
    minScore(grid) {
        //your code goes here
    }
}

csharp

class Solution
{
    public int[][] MinScore(int[][] grid)
    {
        //your code goes here
    }
}

func minScore(grid [][]int) [][]int {
}

Stuck? Show a way to structure it+

01Binary-search a candidate maximum cell value.
02Check reachability using only cells at or below it.
03Use BFS or DFS from the start.
04Move low or high by feasibility.
05Return the first feasible threshold.

Reference answer

For a minimax grid problem, do not optimize paths directly first. Binary-search a value T and ask the monotonic question: can the required route be completed using only cells whose value is at most T? Run BFS or DFS from the start, rejecting any cell above T; if the destination is reached, T is feasible and higher thresholds are also feasible, otherwise it is too low. Search from the minimum possible cell value to the maximum. This makes correctness easy: the predicate changes only once from false to true. A feasibility check costs O(R*C), so total time is O(R*C*log V) and space O(R*C) for visited state. A Dijkstra minimax solution is another strong answer when values are large or direct path reconstruction is desired.

Then expect these follow-ups

How does minimax Dijkstra work here?
Tests: graph optimization
How would you reconstruct the route?
Tests: parents

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question