FastPrepSafest Mouse Path Away from a Cat
Problems/Safest Mouse Path Away from a Cat

Safest Mouse Path Away from a Cat

Google logoGoogle● HardFULLTIMEPHONE SCREEN
QuestionFunctionExamplesConstraints

Problem statement

Source note: The interview report asks for a land path from the mouse to the cheese that maximizes the path's minimum Manhattan distance from a cat. The deterministic grid runner preserves that full capability.

A square grid contains land cells marked 0 and impassable water cells marked 1. A mouse starts at start, wants to reach target, and a cat is located at cat. All three coordinates are land cells.

The mouse may move one cell horizontally or vertically through land. The safety of a path is the minimum Manhattan distance from any cell on that path to the cat. Return the maximum possible safety among all mouse paths from start to target, or -1 when no path exists.

Function

maximumMouseSafety(grid: int[][], start: int[], target: int[], cat: int[]) → int

Examples

Example 1

grid = [[0,0,0],[0,0,0],[0,0,0]]start = [0,0]target = [2,2]cat = [0,2]return = 2

Following the left and bottom edges keeps every visited cell at Manhattan distance at least 2 from the cat.

Example 2

grid = [[0,1,0],[0,1,0],[0,0,0]]start = [0,0]target = [0,2]cat = [1,2]return = 0

The water wall forces every route through the cat cell before reaching the target, so the minimum distance is 0.

Example 3

grid = [[0,1],[1,0]]start = [0,0]target = [1,1]cat = [0,0]return = -1

Water separates the two land cells.

Constraints

  • 1 <= grid.length == grid[i].length <= 500.
  • Every grid value is 0 or 1.
  • start, target, and cat each contain two in-range coordinates on land.

More Google problems

  • Apartment Housemate PreferencesPHONE SCREEN · Seen Nov 2026
  • Price at Query TimestampsPHONE SCREEN · Seen Nov 2026
  • 0/1 Knapsack with Weight and Volume LimitsONSITE INTERVIEW · Seen Nov 2026
All Google interview questionsSee Google hiring insights
Saved
class Solution {
    public int maximumMouseSafety(int[][] grid, int[] start, int[] target, int[] cat) {
        // Write your solution here.
    }
}
Checking account…