Frontend School

Scenic Route Finder

DSA
medium

Scenic Route Finder

Medium
Recursion
Backtracking
Grid

Overview

Uber's mapping and routing systems are crucial for efficient operations. Beyond just the fastest route, sometimes we need to consider alternative factors, like a "scenic value" for premium rides or specialized deliveries. This problem simulates a scenario where we need to identify all possible routes that meet a specific "scenic sum" criterion, mimicking a feature that might enhance rider experience or optimize specialized delivery logistics.

What you need to do / Task

Implement a function findAllScenicPaths that takes a grid representing a city map, a start coordinate, an end coordinate, and a target scenic sum. The function should return all unique paths from the start to the end cell where the sum of scenic values of all cells in the path (including start and end) exactly equals targetScenicSum.

Input & output

  • grid: number[][] - A 2D array where grid[r][c] represents the scenic value of the cell at row r and column c.

  • start: [number, number] - A tuple [r, c] indicating the starting cell coordinates.

  • end: [number, number] - A tuple [r, c] indicating the ending cell coordinates.

  • targetScenicSum: number - The exact sum of scenic values that a valid path must achieve.

  • Returns: string[][] - An array of unique paths. Each path is represented as an array of strings, where each string is a cell coordinate in "row,col" format (e.g., "0,0", "1,0"). The order of paths in the output array does not matter. If no such paths exist, return an empty array.

Clarifications

  • Movement is restricted to 4 directions: up, down, left, right. Diagonal moves are not allowed.
  • A cell cannot be revisited within the same path. This means a path must be simple.
  • The start and end cells are always within the grid boundaries.
  • The path must include both the start and end cells. Their scenic values contribute to the targetScenicSum.

Examples

1

Example 1

Input:

grid = [[1, 2], [3, 4]], start = [0, 0], end = [1, 1], targetScenicSum = 8

Output:

[["0,0","1,0","1,1"]]

Note:

Path (0,0) -> (1,0) -> (1,1) has scenic values 1 + 3 + 4 = 8, matching the target. Path (0,0) -> (0,1) -> (1,1) has sum 1 + 2 + 4 = 7, which is not 8.

2

Example 2

Input:

grid = [[1, 2, 1], [3, 4, 5], [6, 7, 8]], start = [0, 0], end = [2, 2], targetScenicSum = 21

Output:

[["0,0","1,0","1,1","1,2","2,2"]]

Note:

Path (0,0) -> (1,0) -> (1,1) -> (1,2) -> (2,2) has scenic values 1 + 3 + 4 + 5 + 8 = 21, matching the target.

3

Example 3

Input:

grid = [[1, 1], [1, 1]], start = [0, 0], end = [1, 1], targetScenicSum = 10

Output:

[]

Note:

The maximum possible scenic sum for any valid path from (0,0) to (1,1) in this grid is 3 (e.g., 1+1+1). No path can sum to 10.

Constraints

Constraints & assumptions

  • 1 <= grid.length, grid[0].length <= 10 (Grid dimensions M x N)
  • 0 <= grid[r][c] <= 100 (Scenic value of each cell)
  • 0 <= targetScenicSum <= 1000
  • start[0], end[0] are valid row indices.
  • start[1], end[1] are valid column indices.
  • There are no obstacles; all cells are traversable.

Out of scope

  • Optimizing for the shortest or longest path.
  • Handling varying movement costs or complex terrain types beyond scenic value.
  • Parallel processing for path discovery.

What interviewers evaluate

  • Correct application of recursion/backtracking to explore paths.
  • Ability to manage path state (current path, current sum, visited cells) effectively.
  • Handling base cases and recursive steps accurately.
  • Code clarity, organization, and adherence to best practices.

Loading editor...