Find Optimal Commute

Problem Overview

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)
• A digit from '1' to k: A street segment reserved for exactly one transportation mode
• 'X': An impassable roadblock

You'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 mode
• costs: The cost (in dollars) to traverse a single block using each mode

Movement Rules

• Movement is allowed up, down, left, and right only (no diagonal movement)
• You may only travel along contiguous cells of the same transportation mode (i.e., same digit)
• You cannot switch modes mid-journey in the base problem
• You cannot move between cells of different modes, nor can you cross roadblocks ('X')
• A valid route must traverse at least one digit cell; moving directly from an adjacent 'S' to 'D' is not a valid commute

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 contribute neither time nor cost.

Objective

Return the name of the transportation mode that yields the minimum total time from 'S' to 'D'.

• If multiple modes result in the same minimum time, return the one with the lowest total cost
• If multiple modes also tie on total cost, returning any tied mode is acceptable
• Return an empty string "" if no valid route exists

Example

Input:

grid = [
    ['S', '1', '1', '1', 'D'],
    ['2', '2', '2', '2', 'X']
]

modes = ["bike", "bus"]
times = [5, 3]
costs = [2, 1]

Explanation:

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

  • S (0,0) → (0,1) → (0,2) → (0,3) → D (0,4)
  • Distance: 3 mode cells traversed
  • Time: 3 × 5 = 15 minutes
  • Cost: 3 × 2 = 6 dollars

• Mode 2 (bus): Cannot reach D

  • S (0,0) → (1,0) → (1,1) → (1,2) → (1,3) → blocked by X at (1,4)
  • No path to D

Output:

"bike"  # Only valid route with 15 minutes

Constraints

• 1 <= grid.length, grid[0].length <= 100 (rows × columns)
• 1 <= k <= 4 (number of transportation modes)
• modes.length == times.length == costs.length == k
• 1 <= times[i], costs[i] <= 100
• Grid contains exactly one 'S' and one 'D'

Approach 1: Per-Mode BFS

Algorithm

For each transportation mode: [Source: darkinterview.com]

1. Run a BFS starting from 'S'
2. Only traverse cells that match the current mode's digit
3. Track the shortest path length to reach 'D'
4. Calculate total time and cost for this mode

After all BFS runs, compare results and return the optimal mode.

Time Complexity

• O(r × c + k), which is O(r × c) under the given constraints
• The initial scan takes O(r × c). Although we start one BFS per mode, the mode cells are disjoint: a digit cell can only be visited by the BFS for its own mode. The k searches add only O(k) initialization overhead beyond the total number of visited cells.

Space Complexity

• O(r × c) for the visited set and queue

Implementation:

from 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]

                    
                    can_enter_dest = cell ==   dist > 
                     cell == mode_digit  can_enter_dest:
                        visited.add((nr, nc))
                        
                        new_dist = dist  cell ==   dist + 
                        queue.append((nr, nc, new_dist))

     best_mode

Approach 2: Single-Pass BFS

We can also run one BFS from the start and explore all modes simultaneously by tracking which mode each queued path uses. This avoids maintaining a separate queue for every mode, although it does not improve the asymptotic complexity under this fixed-cell model.

Algorithm

1. Start BFS from 'S', adding every adjacent digit cell to the queue. Do not enqueue 'D' directly because a valid route must use at least one mode cell
2. For each cell in the queue, track (row, col, mode_used, distance)
3. Only add a neighbor to the queue if:
   • It matches the current mode being used, OR
   • It's the destination 'D'
4. Track visited states as (row, col, mode)
5. When reaching 'D', calculate time and cost, and update the best result

Key Insight

By tracking (row, col, mode) in the visited set, we ensure each state is processed at most once. [Source: darkinterview.com]

Crucially: Each digit cell has a fixed mode (for example, a '1' cell can only be visited using mode 1). Therefore, each reachable digit cell is visited at most once. The destination may be reached once per mode because (D, mode) states are distinct.

Like the per-mode approach, this processes O(r × c + k) states in total. Its benefit is using one coordinated traversal rather than improving the worst-case asymptotic bound.

Time Complexity

• O(r × c + k), which is O(r × c) under the given constraints
• Each digit cell is visited at most once, and the destination is processed at most once per mode

Space Complexity

• O(r × c) for the visited set and queue

Implementation:

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, -), (-, )]:
        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

Follow-Up 1: Allow Mode Switching with Cost

Question: What if you can switch transportation modes mid-journey, but each switch incurs an additional switch_cost dollars and switch_time minutes? [Source: darkinterview.com]

Modified Problem

• You may move between adjacent digit cells with different modes
• Moving from a mode-a cell into a mode-b cell, where a != b, counts as one switch and adds switch_cost dollars and switch_time minutes
• Choosing the first mode when leaving 'S' does not count as a switch
• Assume switch_time >= 0 and switch_cost >= 0
• Minimize total travel time; among routes with the same total time, minimize total cost
• Return the route as a list of coordinates, including 'S' and 'D', together with its total time and total cost. Return None if no route exists

Solution Approach

Use Dijkstra's algorithm with a priority queue:

1. State: (total_time, total_cost, row, col, current_mode)
2. Priority: Sort by (total_time, total_cost) (time first, then cost)
3. Maintain the shortest-known (time, cost) for each (row, col, mode) state
4. When exploring neighbors:
   • Derive the neighbor's mode directly from its digit (next_mode_idx = int(cell) - 1)
   • Same mode: Add normal travel time/cost
   • Different mode: Add travel time/cost + switch penalties
5. Record a predecessor whenever a state improves, then follow those pointers backward from 'D' to reconstruct the route

In this grid model, each non-special cell has exactly one mode digit, so trying every possible mode at every cell is unnecessary. We explore the four neighboring cells, and each neighbor's digit determines the next mode. Keeping current_mode in the state makes the switch calculation explicit and supports variants in which a cell allows multiple modes.

A plain DFS with memoization is not a good fit because the grid is a cyclic, weighted graph rather than a DAG. Dijkstra's algorithm safely settles states in optimal (time, cost) order. If a generalized version allows several modes at one cell, memoizing by coordinate alone would also be insufficient; the current mode must be part of the state. [Source: darkinterview.com]

The coordinate route fully identifies the mode sequence because every traversed digit cell maps to exactly one mode.

Time Complexity

• This grid model: O((r × c) log(r × c)), because both the number of states and the number of grid edges are O(r × c)
• Generalized multi-mode variant: O((V + E) log V), where V is the number of (cell, mode) states and E is the number of valid transitions between them

Space Complexity

• O(r × c) in this grid model for the priority queue, best-known distances, and predecessor map

Implementation:

import heapq
from typing import List, Optional, Tuple

Coordinate = Tuple[int, int]
CommuteResult = Tuple[List[Coordinate], int, int]

def findOptimalCommuteWithSwitching(grid: List[List[str]], modes: List[str],
                                    times: List[int], costs: List[int],
                                    switch_time: int,
                                    switch_cost: int) -> Optional[CommuteResult]:
    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 None

    # Use mode -1 only for the initial state at S.
    start_state = (start[0], start[1], -1)

    # Priority queue: (total_time, total_cost, row, col, mode_idx)
    pq = [(, , start[], start[], -)]
    best = {start_state: (, )}
    parent = {}

     pq:
        curr_time, curr_cost, r, c, mode_idx = heapq.heappop(pq)
        state = (r, c, mode_idx)

        
         best.get(state) != (curr_time, curr_cost):
            

         (r, c) == dest:
            path = []
            current = state
             :
                path.append((current[], current[]))
                 current == start_state:
                    
                current = parent[current]
            path.reverse()
             path, curr_time, curr_cost

        
         dr, dc  [(, ), (, ), (, -), (-, )]:
            nr, nc = r + dr, c + dc

              <= nr < rows   <= nc < cols:
                cell = grid[nr][nc]

                 cell == :
                    
                     mode_idx == -:
                        
                    next_mode_idx = mode_idx
                    new_time, new_cost = curr_time, curr_cost
                 cell.isdigit():
                    next_mode_idx = (cell) - 
                    new_time = curr_time + times[next_mode_idx]
                    new_cost = curr_cost + costs[next_mode_idx]

                    
                     mode_idx != -  next_mode_idx != mode_idx:
                        new_time += switch_time
                        new_cost += switch_cost
                :
                    
                    

                next_state = (nr, nc, next_mode_idx)
                candidate = (new_time, new_cost)
                 candidate < best.get(next_state, ((), ())):
                    best[next_state] = candidate
                    parent[next_state] = state
                    heapq.heappush(
                        pq,
                        (new_time, new_cost, nr, nc, next_mode_idx)
                    )

     

Follow-Up 2: Limited Number of Mode Switches

Question: What if you can switch modes at most max_switches times?

Return the same route, total time, and total cost as in Follow-Up 1, subject to the switch limit. [Source: darkinterview.com]

Solution Approach

Modify the Dijkstra's algorithm to include the number of switches in the state:

1. State: (total_time, total_cost, row, col, current_mode, switches_used)
2. Track: best[row][col][mode][switches_used]
3. Only allow switching if switches_used < max_switches

Time Complexity

• Fixed-digit grid: O(r × c × (max_switches + 1) × log(r × c × (max_switches + 1)))
• For a generalized model with multiple modes per cell, express the bound as O((V + E) log V) over the expanded states and transitions

Space Complexity

• O(r × c × (max_switches + 1)) for the fixed-digit grid