Leetcode - Infinite Taxi Driver

Medium

Jan 14, 2026

#graph

#bfs

Infinite Taxi Driver

In an alternate world, we encounter a remarkable city characterized by a perfect grid system. The city's roads run exclusively north-south and east-west, forming a grid where each block is a 1-mile by 1-mile square, with parallel roads spaced 1 mile apart. This grid extends infinitely in all directions. Each intersection on this grid can be represented as a coordinate point (x, y) (x, y). As a taxi driver, you start at a specific location with the goal of reaching your destination. However, you are restricted to driving only along the city's roads, meaning you can move solely in the cardinal directions: north, south, east, and west.

Legend:
         C: Cab
         D: Destination
         Initial Grid:
                    Infinitely More Expansions
                      . . . . . . . . . . .
                    Y . . . . . . . . . . .
                ... 6 _ _ _ _ _ _ _ _ _ _ _ ...
                ... 5 _ _ _ _ _ _ _ _ _ _ _ ...
                ... 4 _ _ _ _ _ _ _ _ _ _ _ ...
                ... 3 _ _ _ _ _ _ _ _ D _ _ ...
                ... 2 _ _ _ _ _ _ _ _ _ _ _ ...
                ... 1 _ _ _ _ _ _ _ _ _ _ _ ...
                ... 0 _ _ _ C _ _ _ _ _ _ _ ...
                     0 1 2 3 4 5 6 7 8 9 10 X
                      . . . . . . . . . . .
                      . . . . . . . . . . .
                    Infinitely More Expansions

We now introduce the concept of barriers. Barriers are placed at specific intersections, preventing the taxi driver from passing through them.

Given the presence of these barriers, there are two objectives:

Determine the shortest possible route the driver can take to reach their destination. Determine the minimum time required for the driver to reach the destination, assuming each step the taxi takes is equivalent to 1 second.

Legend:
        C: Cab
        D: Destination
        X: Barrier
                        
Grid with Barriers:
  
    Infinitely More Expansions
      . . . . . . . . . . .
    Y . . . . . . . . . . .
... 6 _ _ _ _ _ _ _ _ _ _ _ ...
... 5 _ _ _ _ _ _ _ _ _ _ _ ...
... 4 _ _ _ _ _ _ _ X _ _ _ ...
... 3 _ _ _ _ _ _ _ X D _ _ ...
... 2 _ _ _ _ _ _ _ X X _ _ ...
... 1 _ _ _ _ _ _ _ X _ _ _ ...
... 0 _ _ _ C _ _ _ X _ _ _ ...
     0 1 2 3 4 5 6 7 8 9 10 X
      . . . . . . . . . . .
      . . . . . . . . . . .

    Infinitely More Expansions

Example 1:

Input:         
        Cab: (3,0)
        Destination: (8,3)
        Barriers: (7,0), (7,1), (7, 2), (7,3), (7,4), (8,2)
Output:
            any path of length 12 is a valid solution.
                        path = "NNNNNEEEEESS"
                        path = "SEEEEEENNNNW"

[execution time limit] 3 seconds (java) [memory limit] 2g

Notes

Intuition

On an infinite grid with barriers, BFS finds the shortest path. Each cell has 4 neighbors (N, S, E, W), and we track the path as a string of directions.

Implementation

Generate neighbors as (direction, coordinate) pairs. No bounds checking needed on an infinite grid. BFS from start with queue entries of (coordinate, path_string). Track visited coordinates. For each neighbor, skip if visited or a barrier. If it's the destination, return the accumulated path. Otherwise, add to queue with the extended path.

Edge-cases

If start equals destination, return empty string. The algorithm guarantees the shortest path due to BFS properties. Could be optimized with A* using Manhattan distance heuristic.

Time: O(V) — where V is the number of reachable states
Space: O(V) — visited set and queue

Complexity

Solution

from typing import List, Tuple
from collections import deque

class Solution:
    def neighbours(self, coord: Tuple[int, int]) -> List[Tuple[str, Tuple[int, int]]]:
        dirs = [("N", (0, 1)), ("S", (0, -1)), ("W", (-1, 0)), ("E", (1, 0))]
        result = []
        x, y = coord
        for cardinal, dir in dirs:
            dx, dy = dir
            nx, ny = x + dx, y + dy 
            result.append((cardinal, (nx, ny)))
        return result
    
    def manhattan(self, a: Tuple[int, int], b: Tuple[int, int]) -> int:
        return abs(a[0] - b[0]) + abs(a[1] - b[1])

    def findPath(self, cab: Tuple[int, int], destination: Tuple[int, int], barriers: List[Tuple[int,int]]) -> str:
        if cab == destination:
            return ""

        q = deque([(cab, "")])
        visited = set([cab])
        blocked = set(barriers)
        while q:
            curr, path = q.popleft()
            for n_dir, n_coord in self.neighbours(curr):
                if n_coord in visited or n_coord in blocked:
                    continue
                if n_coord == destination:
                    return path + n_dir
                
                q.append((n_coord, path + n_dir))
                visited.add(n_coord)
        return ""

if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()