You are commuting across a simplified map of San Francisco, represented as a 2D grid. Each cell on the grid is one of the following:
'S': Your home location (starting point)'D': Your office location (destination)'1' to k: A street segment reserved for exactly one transportation mode'X': An impassable roadblockYou're also given three arrays with length k:
modes: The name of each available transportation mode (e.g., ["bike", "bus", "walk", "scooter"])times: The time (in minutes) required to traverse a single block using each modecosts: The cost (in dollars) to traverse a single block using each mode'X')For each mode i (0-indexed), the time and cost to traverse a single block are given by times[i] and costs[i], respectively. [Source: darkinterview.com]
The total travel time and total cost are calculated as the sum of the time and cost for each mode cell traversed along the path from 'S' to 'D'. Note that 'S' and 'D' are special cells (not mode cells) and do not contribute to the cost.
Return the name of the transportation mode that yields the minimum total time from 'S' to 'D'.
"" if no valid route existsgrid = [
['S', '1', '1', '1', 'D'],
['2', '2', '2', '2', 'X']
]
modes = ["bike", "bus"]
times = [5, 3]
costs = [2, 1]
Grid layout: [Source: darkinterview.com]
Row 0: S 1 1 1 D
Row 1: 2 2 2 2 X
Mode 1 (bike): Path exists from S to D
Mode 2 (bus): Cannot reach D
"bike" # Only valid route with 15 minutes
1 <= grid.length, grid[0].length <= 100 (rows × columns)1 <= k <= 4 (number of transportation modes)modes.length == times.length == costs.length == k1 <= times[i], costs[i] <= 100'S' and one 'D'For each transportation mode: [Source: darkinterview.com]
'S''D'After all BFS runs, compare results and return the optimal mode.
k = number of modesr = number of rowsc = number of columnsk times, and each BFS visits O(r × c) cellsfrom collections import deque
from typing import List
def findOptimalCommute(grid: List[List[str]], modes: List[str],
times: List[int], costs: List[int]) -> str:
rows, cols = len(grid), len(grid[0])
# Find start and destination
start, dest = None, None
for r in range(rows):
for c in range(cols):
if grid[r][c] == 'S':
start = (r, c)
elif grid[r][c] == 'D':
dest = (r, c)
if not start or not dest:
return ""
best_time = float('inf')
best_cost = float('inf')
best_mode = ""
# Try each transportation mode
for mode_idx in range(len(modes)):
mode_digit = str(mode_idx + 1)
# BFS for this mode
queue = deque([(start[0], start[1], 0)]) # (row, col, distance)
visited = {start}
found =
queue found:
r, c, dist = queue.popleft()
(r, c) == dest:
total_time = dist * times[mode_idx]
total_cost = dist * costs[mode_idx]
(total_time < best_time
(total_time == best_time total_cost < best_cost)):
best_time = total_time
best_cost = total_cost
best_mode = modes[mode_idx]
found =
dr, dc [(, ), (, ), (, -), (-, )]:
nr, nc = r + dr, c + dc
( <= nr < rows <= nc < cols
(nr, nc) visited):
cell = grid[nr][nc]
cell == mode_digit cell == :
visited.add((nr, nc))
new_dist = dist cell == dist +
queue.append((nr, nc, new_dist))
best_mode
The key insight is that we can run one BFS from the start and explore all modes simultaneously by tracking which mode each cell belongs to.
'S', adding all adjacent cells (regardless of mode) to the queue(row, col, mode_used, distance)'D'(row, col, mode))'D', calculate time and cost, and update the best resultBy tracking (row, col, mode) in the visited set, we ensure each (cell, mode) pair is processed at most once. [Source: darkinterview.com]
Crucially: Each grid cell has a fixed mode digit (e.g., '1', '2', etc.). A cell with mode '1' can only be visited when traveling using mode 1. Therefore, although we track (row, col, mode) in the visited set, each cell is visited exactly once (by its designated mode), not k times.
This gives us O(r × c) total cell visits instead of O(k × r × c).
from collections import deque
from typing import List
def findOptimalCommuteOptimized(grid: List[List[str]], modes: List[str],
times: List[int], costs: List[int]) -> str:
rows, cols = len(grid), len(grid[0])
# Find start and destination
start, dest = None, None
for r in range(rows):
for c in range(cols):
if grid[r][c] == 'S':
start = (r, c)
elif grid[r][c] == 'D':
dest = (r, c)
if not start or not dest:
return ""
best_time = float('inf')
best_cost = float('inf')
best_mode = ""
# Single BFS: (row, col, mode_used, distance)
# mode_used is the digit of the transportation mode
queue = deque()
visited = set()
# Initialize: explore all neighbors of start
for dr, dc in [(0, 1), (1, 0), (0, -1), (-, )]:
nr, nc = start[] + dr, start[] + dc
<= nr < rows <= nc < cols:
cell = grid[nr][nc]
cell.isdigit():
mode_digit = cell
visited.add((nr, nc, mode_digit))
queue.append((nr, nc, mode_digit, ))
queue:
r, c, mode_digit, dist = queue.popleft()
grid[r][c] == :
mode_idx = (mode_digit) -
total_time = dist * times[mode_idx]
total_cost = dist * costs[mode_idx]
(total_time < best_time
(total_time == best_time total_cost < best_cost)):
best_time = total_time
best_cost = total_cost
best_mode = modes[mode_idx]
dr, dc [(, ), (, ), (, -), (-, )]:
nr, nc = r + dr, c + dc
( <= nr < rows <= nc < cols
(nr, nc, mode_digit) visited):
cell = grid[nr][nc]
cell == mode_digit cell == :
visited.add((nr, nc, mode_digit))
new_dist = dist cell == dist +
queue.append((nr, nc, mode_digit, new_dist))
best_mode
Question: What if you can switch transportation modes mid-journey, but each switch incurs an additional cost of x dollars (and potentially additional time t minutes)? [Source: darkinterview.com]
switch_cost dollars and switch_time minutes to the totalUse Dijkstra's algorithm with a priority queue:
(total_time, total_cost, row, col, current_mode)(total_time, total_cost) (time first, then cost)best[row][col][mode] to track the best time/cost to reach each cell with each modek times (once per mode)import heapq
from typing import List
def findOptimalCommuteWithSwitching(grid: List[List[str]], modes: List[str],
times: List[int], costs: List[int],
switch_time: int, switch_cost: int) -> str:
rows, cols = len(grid), len(grid[0])
# Find start and destination
start, dest = None, None
for r in range(rows):
for c in range(cols):
if grid[r][c] == 'S':
start = (r, c)
elif grid[r][c] == 'D':
dest = (r, c)
if not start or not dest:
return ""
# Priority queue: (total_time, total_cost, row, col, mode_idx)
pq = []
# Initialize with all modes from start
for dr, dc in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
nr, nc = start[0] + dr, start[1] + dc
if 0 <= nr < rows <= nc < cols:
cell = grid[nr][nc]
cell.isdigit():
mode_idx = (cell) -
heapq.heappush(pq, (times[mode_idx], costs[mode_idx], nr, nc, mode_idx))
best = {}
pq:
curr_time, curr_cost, r, c, mode_idx = heapq.heappop(pq)
state = (r, c, mode_idx)
state best:
best_time, best_cost = best[state]
(curr_time > best_time
(curr_time == best_time curr_cost >= best_cost)):
best[state] = (curr_time, curr_cost)
grid[r][c] == :
modes[mode_idx]
dr, dc [(, ), (, ), (, -), (-, )]:
nr, nc = r + dr, c + dc
<= nr < rows <= nc < cols:
cell = grid[nr][nc]
cell == :
cell == :
next_state = (nr, nc, mode_idx)
next_state best:
best_time, best_cost = best[next_state]
(curr_time > best_time
(curr_time == best_time curr_cost >= best_cost)):
heapq.heappush(pq, (curr_time, curr_cost, nr, nc, mode_idx))
next_mode_idx ((modes)):
next_mode_digit = (next_mode_idx + )
cell != next_mode_digit:
new_time = curr_time + times[next_mode_idx]
new_cost = curr_cost + costs[next_mode_idx]
next_mode_idx != mode_idx:
new_time += switch_time
new_cost += switch_cost
next_state = (nr, nc, next_mode_idx)
next_state best:
best_time, best_cost = best[next_state]
(new_time > best_time
(new_time == best_time new_cost >= best_cost)):
heapq.heappush(pq, (new_time, new_cost, nr, nc, next_mode_idx))
Question: What if you can switch modes at most max_switches times?
Modify the Dijkstra's algorithm to include the number of switches in the state: [Source: darkinterview.com]
(total_time, total_cost, row, col, current_mode, switches_used)best[row][col][mode][switches_used]switches_used < max_switches"" (e.g., D is surrounded by 'X' or wrong mode cells)""""""