Answer Repeated Shortest Increasing-Path Queries

Given an integer grid, repeatedly find a shortest strictly increasing path from the top-left cell to a requested target value. Moves are allowed up, right, down, and left. Return the values along the path, or an empty path if the target is absent or unreachable.

Implement increasing_paths(grid: int[][], targets: int[]) -> int[][], returning one value path per target in input order.

Constraints & Assumptions

• The grid is rectangular, with 1 through 100 rows and columns, and at most 1,000 target queries.
• Values are distinct signed 32-bit integers. The source does not specify duplicates; uniqueness is an explicit practice assumption so each target identifies one cell.
• A move is legal only if the next cell's value is strictly greater than the current value.
• Path length is measured in number of edges. The starting cell has a zero-edge path containing its own value.
• Resolve equal-length paths using the first discovery in a FIFO BFS that visits neighbors in this order: up, right, down, left. This is a deterministic tie convention for the source's any-shortest-path output.
• Preprocess the fixed grid once. Do not run a full new traversal for every query; each answer should require only lookup and output-path reconstruction after preprocessing.

Examples

grid = [[1,2,3],[4,5,8],[7,9,6]]
targets = [5,6,1]
result = [[1,2,5],[],[1]]

grid = [[4,3],[5,6]]
targets = [6,3,9]
result = [[4,5,6],[],[]]

Explain the preprocessing and per-query time and space costs. Compare storing a complete path at every reachable cell with storing one distance/predecessor per cell, including the cost of actually returning a long path. Discuss why a shortest-path traversal or equivalent dynamic program can reuse work across calls.

Hint: Retain how each cell was first reached

Once shortest reachability from the fixed start is known, a query can follow saved predecessor links instead of exploring the grid again.

Preprocess Shortest Increasing Grid Paths for Repeated Queries

Approach

Build a value-to-cell lookup, then run one FIFO BFS from the top-left cell over legal strictly increasing edges. Scan neighbors exactly up, right, down, left and set a predecessor only on first discovery. BFS visits cells in nondecreasing edge distance, so that first predecessor gives a shortest path. The fixed queue and neighbor order also fix ties exactly as required. Marking on discovery prevents later arrivals from changing the selected path. The start uses a predecessor sentinel distinct from the unreachable sentinel. For each target, lookup absence or unreachable state yields an empty list; otherwise follow predecessor links to the start and reverse the collected values. This returns the start itself as a singleton and naturally preserves repeated-query order. With V cells and at most four edges per cell, preprocessing takes O(V) expected time and O(V) state. A query takes expected O(1) lookup plus O(path length) reconstruction and returned storage, which cannot be avoided when actually emitting the path. Storing a full path at every cell can require O(V^2) total path entries on a long corridor; one predecessor per cell avoids that duplication. Strict increases also form a DAG, so a suitable shortest-path dynamic program could share work, but it must reproduce the specified FIFO tie rule to return the same paths.

• Time complexity: O(R*C) expected preprocessing, then O(1 + returned path length) per query
• Space complexity: O(R*C) preprocessing state plus returned paths