Shortest Path in Constrained Grid — Problem Statement & Solution Guide

GraphsMediumMixed

TimeO(M\times N)

SpaceO(M\times N)

Problem Description

You are given a grid of size MxN, where each cell has a unique encryption key. The goal is to find the shortest path from the top-left cell to the central cell, given that you can move only a certain number of steps in any direction (up, down, left, right) and must follow one of the predefined possible paths. The grid size, possible paths, and movement constraints should be clearly defined.

DSA Pattern Breakdown

"Shortest Path in Constrained Grid"

medium

WHY DOES IT MATTER?

BFS guarantees the shortest path in an unweighted graph, which is essential when the objective is minimal moves. It systematically explores all nodes at a given distance before moving deeper, ensuring optimality without exhaustive search.

OPTIMIZATION CHALLENGE

The key insight is that you only need to visit each cell once. By marking cells as visited when they are enqueued, you eliminate redundant work and keep the queue size bounded to O(MN).

REAL-WORLD CONNECTION

Consider packet routing in a network where each hop has equal cost; routers use BFS‑like flooding to find the minimal hop count. Similarly, autonomous drones navigate grids by exploring reachable waypoints level by level to avoid unnecessary detours.

Always precompute the set of valid moves for each cell or encode them as offsets; this keeps the inner loop tight and lets the compiler optimize the loop, which is critical under interview time constraints.

COMPLEXITY AT A GLANCE

⏱ Time:O(M\times N)

💾 Space:O(M\times N)

Core Theory — Why This Approach?

The problem reduces to finding the shortest path in an unweighted directed graph where each grid cell is a node and edges exist only for the predefined allowed moves (e.g., jump 2 cells right, 1 cell down, etc.). A naive depth‑first search or recursive backtracking would explore all possible sequences of moves, leading to exponential time complexity and quickly becoming infeasible for large M and N. The optimal paradigm is Breadth‑First Search (BFS) because it explores nodes level by level, guaranteeing that the first time we reach the target cell we have used the minimal number of moves. By representing the grid as a graph and using a queue to process cells in order of distance, we achieve linear time in the number of reachable cells, while a visited set prevents revisiting nodes and keeps the space usage bounded.

Interview Questions on This Problem

Q1How would you modify the classic BFS algorithm to handle a grid where each move can skip multiple cells (e.g., jump 3 cells right) instead of moving only to adjacent cells?

Treat each allowed jump as a single edge in the graph. For each cell, precompute all destination cells reachable by the allowed jumps and enqueue them during BFS. The rest of the BFS logic remains unchanged, ensuring optimality while handling variable step sizes.

Q2In a production system, you need to find the shortest path for a robot in a warehouse grid with obstacles and variable step constraints. What data structures would you use to maintain performance and why?

Use a 2D array or hash map to represent the grid and a boolean visited matrix to avoid revisits. A double-ended queue (deque) can be used for BFS; if edge weights vary, a priority queue (min‑heap) for Dijkstra. For large sparse grids, a sparse adjacency list or coordinate compression can reduce memory.

Q3During an interview, a candidate proposes a recursive DFS with memoization for this problem. What are the potential pitfalls of that approach compared to BFS?

DFS with memoization may still explore many paths before finding the shortest because it follows depth first, potentially reaching deep nodes before shallow ones. Memoization only avoids recomputing subproblems but does not guarantee minimal steps. BFS inherently finds the shortest path in an unweighted graph, making it more reliable for this problem.

Examples

Example 1

Input

grid = [[1, 2, 3], [4, 5, 6], [7, 8, 9]], movementConstraints = [1, 1], possiblePaths = [[0, 0], [0, 1], [1, 1], [1, 2], [2, 2]]

Output

Shortest path: [[0, 0], [0, 1], [1, 1], [1, 2], [2, 2]]

Explanation: Step-by-step: with input grid and movement constraints, we can move from the top-left cell to the central cell by following the possible paths, giving the shortest path as the output

Example 2

Input

grid = [[1, 2], [3, 4]], movementConstraints = [1, 1], possiblePaths = [[0, 0], [0, 1], [1, 1]]

Output

Shortest path: [[0, 0], [0, 1], [1, 1]]

Explanation: Step-by-step: with input grid and movement constraints, we can move from the top-left cell to the central cell by following the possible paths, giving the shortest path as the output

Constraints

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

Optimal Approach & Strategy

Model the grid as a graph and run BFS, enqueuing each cell once and marking it visited. This guarantees the shortest path in linear time relative to the number of cells.

Brute Force Approach

Try every possible sequence of moves recursively, backtracking when you hit a dead end. This explores all paths and has exponential time complexity, making it impractical for large grids.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(M\times N)

function solution(grid, movementConstraints, possiblePaths) {
       // Define the directions for movement
       const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
       
       // Initialize the queue for BFS
       const queue = [[0, 0, []]];
       
       // Perform BFS to find the shortest path
       while (queue.length > 0) {
           const [x, y, path] = queue.shift();
           path.push([x, y]);
           
           // Check if the current cell is the central cell
           if (x === Math.floor(grid.length / 2) && y === Math.floor(grid[0].length / 2)) {
               return path;
           }
           
           // Explore the neighbors
           for (const [dx, dy] of directions) {
               const nx = x + dx;
               const ny = y + dy;
               
               // Check if the neighbor is within the grid boundaries and has not been visited before
               if (nx >= 0 && nx < grid.length && ny >= 0 && ny < grid[0].length && !path.includes([nx, ny])) {
                   queue.push([nx, ny, [...path]]);
               }
           }
       }
       
       // If no path is found, return an empty array
       return [];
   }

class Solution {
   public:
       vector<vector<int>> solution(vector<vector<int>>& grid, vector<int>& movementConstraints, vector<vector<int>>& possiblePaths) {
           vector<vector<int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
           queue<vector<int>> q;
           q.push({0, 0, 0});
           
           while (!q.empty()) {
               vector<int> current = q.front();
               q.pop();
               int x = current[0];
               int y = current[1];
               int pathLength = current[2];
               
               if (x == grid.size() / 2 && y == grid[0].size() / 2) {
                   vector<vector<int>> path;
                   path.push_back({x, y});
                   for (int i = pathLength - 1; i >= 0; i--) {
                       path.push_back({q.front()[0], q.front()[1]});
                       q.pop();
                   }
                   return path;
               }
               
               for (vector<int> direction : directions) {
                   int nx = x + direction[0];
                   int ny = y + direction[1];
                   
                   if (nx >= 0 && nx < grid.size() && ny >= 0 && ny < grid[0].size()) {
                       q.push({nx, ny, pathLength + 1});
                   }
               }
           }
           
           return {};
       }
   }

class Solution {
       public int[][] solution(int[][] grid, int[] movementConstraints, int[][] possiblePaths) {
           int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
           int[][] queue = new int[grid.length * grid[0].length][3];
           int front = 0, rear = 0;
           queue[rear++] = new int[]{0, 0, 0};
           
           while (front < rear) {
               int x = queue[front][0];
               int y = queue[front][1];
               int pathLength = queue[front][2];
               front++;
               
               if (x == grid.length / 2 && y == grid[0].length / 2) {
                   int[][] path = new int[pathLength + 1][2];
                   path[pathLength] = new int[]{x, y};
                   for (int i = pathLength - 1; i >= 0; i--) {
                       path[i] = queue[i];
                   }
                   return path;
               }
               
               for (int[] direction : directions) {
                   int nx = x + direction[0];
                   int ny = y + direction[1];
                   
                   if (nx >= 0 && nx < grid.length && ny >= 0 && ny < grid[0].length) {
                       queue[rear++] = new int[]{nx, ny, pathLength + 1};
                   }
               }
           }
           
           return new int[0][0];
       }
   }

def solution(grid, movement_constraints, possible_paths):
       directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]
       queue = [(0, 0, [])]
       
       while queue:
           x, y, path = queue.pop(0)
           path = path + [(x, y)]
           
           if x == len(grid) // 2 and y == len(grid[0]) // 2:
               return path
           
           for dx, dy in directions:
               nx, ny = x + dx, y + dy
               
               if (0 <= nx < len(grid) and 0 <= ny < len(grid[0]) and
                       (nx, ny) not in path):
                   queue.append((nx, ny, path))
       
       return []

function solution(grid, movementConstraints, possiblePaths) {
       // Define the directions for movement
       const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
       
       // Initialize the queue for BFS
       const queue = [[0, 0, []]];
       
       // Perform BFS to find the shortest path
       while (queue.length > 0) {
           const [x, y, path] = queue.shift();
           path.push([x, y]);
           
           // Check if the current cell is the central cell
           if (x === Math.floor(grid.length / 2) && y === Math.floor(grid[0].length / 2)) {
               return path;
           }
           
           // Explore the neighbors
           for (const [dx, dy] of directions) {
               const nx = x + dx;
               const ny = y + dy;
               
               // Check if the neighbor is within the grid boundaries and has not been visited before
               if (nx >= 0 && nx < grid.length && ny >= 0 && ny < grid[0].length && !path.includes([nx, ny])) {
                   queue.push([nx, ny, [...path]]);
               }
           }
       }
       
       // If no path is found, return an empty array
       return [];
   }

Asked in Top Tech Interviews

uncategorizedmediumgeneric

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Shortest Path in Constrained Grid Solution

Problem Statement

Input

Output

Input

Output

Constraints

More Graphs

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Shortest Path in Constrained Grid — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor