FastPrepFastPrep
Problem Brief

Reach the End in Time

OA
See Google online assessment and hiring insights

A 2-D grid consisting of some blocked (represented as '#') and some unblocked (represented as '.') cells is given. The starting position of a pointer is in the top-left corner of the grid. It is guaranteed that the starting position is in an unblocked cell, and it is also guaranteed that the bottom-right cell is unblocked. Each cell of the grid is connected with its right, left, top, and bottom cells (if those cells exist). It takes 1 second for a pointer to move from a cell to its adjacent cell. If the pointer can reach the bottom-right corner of the grid within maxTime seconds, return the string 'Yes'. Otherwise, return the string 'No'.

Function Description

Complete the function reachTheEnd in the editor.

reachTheEnd has the following parameter(s):

  1. String[] grid: an array of strings representing the rows of the grid
  2. int maxTime: the maximum time to complete the journey

1Example 1

Input
grid = ["..#", "#.##", "#..."], maxTime = 5
Output
"Yes"
Explanation
..## #.## #... It will take the pointer 5 seconds to reach the bottom-right corner. As long as maxTime >= 5, return 'Yes'.

2Example 2

Input
grid = ["..", ".."], maxTime = 3
Output
"Yes"
Explanation
The grid has 2 rows and 2 columns and the time within which the pointer needs to reach the bottom-right cell is 3 seconds. Starting from the top-left cell, the pointer can either move to the top-right unblocked cell or bottom-left unblocked cell then to the bottom-right cell. It takes 2 seconds to reach the bottom-right cell on either path. Thus, the pointer reachs the bottom-right cell within the 3 seconds allowed, so the answer is "Yes" :)

3Example 3

Input
grid = [".#", "#."], maxTime = 2
Output
"No"
Explanation
The grid has 2 rows and 2 columns and the time within which the pointer needs to reach the bottom-right cell is 2 seconds. It can neither move to the top-right cell is 2 seconds. It can neither move to the top-right cell nor to the bottom-left cell and so the pointer cannot reach the bottom-right cell, regardless of the time constraint.

Constraints

Limits and guarantees your solution can rely on.

  • 1 <= rows <= 500
  • 1 <= maxTime <= 10^5
    • public String reachTheEnd(String[] grid, int maxTime) {
  // write your code here
}
    Input

    grid

    ["..#", "#.##", "#..."]

    maxTime

    5

    Output

    "Yes"

    Sign in to submit your solution.