Click here to Practice
Submit Problem to OJ
Bob Navigates a Maze
Bob and Alice have teamed up on a game show. After winning the first round, they now have access to a maze with hidden gold. If Bob can collect all the gold coins and deliver them to Alice's position, they can split the gold. Bob can move horizontally or vertically as long as he stays in the maze, and the cell is not blocked.
The maze is represented by an n xm array. Each cell has a value, where 0 is open, 1 is blocked, and 2 is open with a gold coin. Bob starts at the top left in cell in (row, column) = (0, 0). Alice's position is given by (x,y). Determine the shortest path Bob can follow to collect all gold coins and deliver them to Alice. If Bob can't collect and give all the gold coins, return -1.
Example: maze = [[0,2,1],[1,2,0],[1,0,0]] with Alice at (2,2) is represented as follows:
B represents Bob's starting position at (0,0), and A represents Alice's position (which will also be Bob's final position). As Bob starts at (0,0), he has two possible paths to collect the gold and deliver to Alice: (0, 0) -> (0, 1) -> (1, 1) -> (2, 1) -> (2, 2) and (0, 0) -> (0, 1) -> (1, 1) -> (1, 2) -> (2, 2). Both paths have a length of 4 and could represent the shortest path.
Complete the function minMoves in the editor below. The function must return the integer length of Bob's shortest path, or -1 if it's not possible.
minMoves has the following parameter(s):
maze[maze...maze[n-1][m-1]]: a 2D array of integers
x: an integer denoting Alice's row coordinate
y: an integer denoting Alice's column coordinate
- 1 <= n,m <= 100
- 0 <= the number of coins <= 10
- 1 <= x < n
- 1 <= y < m
Paths in Warehouse
Click here to Practice
Submit Problem to OJ
There are n players. They have to collect m points. All the players and coins are in 1-D space i.e on a number line. The initial location of all the players is given as the array players where player[i] denotes the location of the ith player. The location of all the points is given as another array point where point[i] denotes the location of the ith point. In one second a player can either move 1 step left or 1 step right or not move at all. A point is considered collected if any of the n players had visited the point's location. The players can move simultaneously and independently of each other every second.
The task is to find the minimum time (in seconds) required to collect all the points if players act optimally.
Note: Locations of players and points are not necessarily given in sorted order.
n = 3, players = [3, 6, 7]
m= 4, points = [2,4,7,9]
All the points can be collected in 2 seconds:
- The first player can collect points at  in one second
- The second player can collect points at  in 2 seconds
- The third player can collect points at [7,9] in 2 seconds, first collecting the point at 7 and then moving to location 9.
It can be proved that we can't collect all the points in less than 2 seconds. Hence the answer is 2.
Complete the function getMinimumTime in the editor below. The function must return an integer, the minimum time required to collect all the points
getMinimumTime has the following parameters:
players[players....players[n-1]]: an array of integers denoting the locations of players
points(points....points[m-1]]: an array of integers denoting the locations of points
- 1 <= n,m <= 10^5
- 1 <= players[i], points[i] <= 109
Closest Random Points
In many real world applications the problem of finding a pair of closest points arises. In the real world, data is usually distributed randomly. Given n points on a plane that are randomly generated with uniform distribution, find the squared shortest distance between pairs of these points.
There are 3 points with x coordinates x = [0, 1, 2] and y = [0, 1, 4]. The points have the xy coordinates (0, 0), (1, 1) and (2, 4). The closest points are (0, 0) and (1, 1), and their squared shortest distance is ((1-0)^2) + ((1-0)^2) = 2.
Complete the function closestSquaredDistance in the editor below.
closestSquaredDistance has the following parameter(s):
int x[n]: each x[i] denotes the x coordinate of the ith point int y[n]: each y[i] denotes the y coordinate of the ith point
long: a long integer that denotes the squared shortest distance between the pairs of points
- 2 <= n
- either n <= 1000 or n = 10^5
- values of x[i] and y[i] are randomly generated with uniform distribution from the range [0, (10^9)-1]