How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Find minimum threshold enabling grid path

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

## Problem You are given an `m x n` integer grid `grid`. You start at the top-left cell `(0, 0)` and want to reach the bottom-right cell `(m-1, n-1)`. You may move **one step** at a time in **4 directions**: up, down, left, right (no diagonals). You may not go outside the grid. Define a threshold value `T`. A path is **valid under threshold `T`** if **every cell value on the path is `<= T`**. ### Task Return the **minimum integer `T`** such that there exists **at least one** valid path from `(0,0)` to `(m-1,n-1)` under threshold `T`. ### Input - `grid`: a 2D array of integers with dimensions `m x n`. ### Output - An integer: the minimum `T` that makes the destination reachable. ### Notes / Constraints (assume) - `1 <= m, n <= 200` - Cell values are integers (may be large; e.g., up to `10^9` in absolute value). - Movement is 4-directional. ### Example If `grid = [[0,2],[1,3]]`, the answer is `3` because you cannot reach the bottom-right without allowing the cell value `3`.

Quick Answer: This question evaluates a candidate's understanding of grid pathfinding, reachability under constraints, and algorithmic optimization, focusing on skills such as graph traversal and handling threshold-based feasibility.

You are given an m x n integer grid. Starting at the top-left cell (0, 0), you want to reach the bottom-right cell (m-1, n-1). You may move one step at a time in 4 directions: up, down, left, or right. For a threshold T, a path is valid if every cell visited on that path has value less than or equal to T. Return the minimum integer T such that at least one valid path exists from the start to the destination.

Constraints

1 <= m, n <= 200
1 <= m * n <= 40000
-10^9 <= grid[i][j] <= 10^9
Movement is allowed only in 4 directions: up, down, left, and right

Examples

Input: ([[0, 2], [1, 3]],)

Expected Output: 3

Explanation: Any path to the bottom-right must include the cell with value 3, so the minimum valid threshold is 3.

Input: ([[0, 100, 2], [1, 2, 2], [3, 4, 1]],)

Expected Output: 2

Explanation: A valid path is 0 -> 1 -> 2 -> 2 -> 1, whose largest value is 2. The cell 100 can be avoided.

Input: ([[-5]],)

Expected Output: -5

Explanation: The start and destination are the same cell, so the threshold only needs to allow that cell.

Input: ([[-3, -2, -1], [-4, 5, 0], [-5, -6, -7]],)

Expected Output: -3

Explanation: A path through the left and bottom edges uses values -3, -4, -5, -6, -7, so the largest value on that path is -3.

Input: ([[7, 7, 7], [7, 7, 7]],)

Expected Output: 7

Explanation: Every possible path consists only of 7s, so the minimum threshold is 7.

Input: ([[5, 1, 7], [4, 8, 2], [3, 6, 0]],)

Expected Output: 6

Explanation: The best route is 5 -> 4 -> 3 -> 6 -> 0, so the minimum possible maximum value along a path is 6.

Hints

Think of the cost of a path as the maximum cell value that appears on it, not the sum of values.
A priority queue can help you always expand the position with the smallest currently known path cost first.

Quick Overview

This question evaluates a candidate's understanding of grid pathfinding, reachability under constraints, and algorithmic optimization, focusing on skills such as graph traversal and handling threshold-based feasibility.