Valid Grid Paths — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Backtracking and solve the Valid Grid Paths problem optimally.
O(K·(m+n)) where K is the number of valid pathsO(m+n) for recursion stack plus O(K·(m+n)) if all paths are storedProblem Description
Given integers m and n representing the number of rows and columns of a rectangular grid, and a list of distinct obstacle cells, compute every possible path from the top-left cell (0,0) to the bottom-right cell (m-1,n-1). From any cell you may move only one step to the right (increase column by 1) or one step down (increase row by 1). A path must never step on a cell that appears in the obstacle list. Return all valid paths as strings composed of the characters 'R' and 'D', sorted in lexicographical order. If no path exists return an empty list.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Valid Grid Paths"
WHY DOES IT MATTER?
Backtracking on grid‑based movement is a foundational pattern for any problem that requires exhaustive enumeration of constrained sequences, such as maze solving, robot motion planning, or generating test cases for UI flows.
OPTIMIZATION CHALLENGE
The key insight is pruning early—by checking bounds and obstacle presence before recursing, we avoid exploring entire sub‑trees that can never lead to a solution, reducing the search space from exponential in m+n to exponential only in the number of feasible paths.
REAL-WORLD CONNECTION
Think of a delivery drone navigating a city block grid while avoiding no‑fly zones; each valid route corresponds to a path that respects right‑and‑down constraints, mirroring how distributed systems route packets around faulty nodes.
During an interview, implement the DFS skeleton first (base case, bounds, obstacle check), then add the path‑building logic; keep the recursion stack minimal and use a mutable list for the current path to avoid costly string concatenations.
COMPLEXITY AT A GLANCE
O(K·(m+n)) where K is the number of valid pathsO(m+n) for recursion stack plus O(K·(m+n)) if all paths are storedCore Theory — Why This Approach?
The problem is a classic combinatorial enumeration on a directed acyclic grid graph where each vertex represents a cell and edges represent allowed moves (right or down). A naive enumeration that tries every sequence of moves without pruning quickly explodes because the number of possible move sequences without obstacles is C(m+n-2, m-1), which grows exponentially with grid dimensions. Introducing obstacles further complicates the search space because many sequences become invalid, but the underlying structure remains a tree of decisions that can be explored efficiently with backtracking. The optimal paradigm is depth‑first search (DFS) with recursion or an explicit stack, combined with pruning: before recursing, we check bounds and obstacle presence, and we backtrack immediately when a dead‑end is reached. This ensures we only generate feasible paths, and each path is built incrementally, yielding a time proportional to the total length of all valid paths and a space proportional to the current recursion depth (at most m+n‑2).
Interview Questions on This Problem
Q1How would you modify the backtracking solution to count the number of valid paths without storing each path?
Replace the path‑building step with a simple integer counter that increments each time the bottom‑right cell is reached; the rest of the DFS remains identical, giving O(#paths) time and O(m+n) space.
Q2If the grid is huge (e.g., 10^5 × 10^5) but the number of obstacles is small, can you compute the number of valid paths efficiently?
Yes—use combinatorial mathematics: the total paths without obstacles is C(m+n-2, m-1); for each obstacle, subtract paths that go through it using inclusion‑exclusion or DP on the sorted obstacle list, achieving O(k log k) where k is the number of obstacles.
Q3Explain how memoization could be applied to this problem and why it may not always be beneficial when enumerating all paths.
Memoization stores the set of paths from a cell to the goal, turning the exponential DFS into a DP that reuses sub‑solutions; however, when the goal is to list every distinct path, memoization would need to store potentially exponential numbers of strings, negating the space savings, so it’s only useful for counting.
Examples
Input
2 2\n0
Output
["DR","RD"]
Explanation: The grid has no obstacles. Two sequences of moves reach the target: Down then Right (DR) and Right then Down (RD).
Input
3 3\n1\n1 1
Output
["DDRR","RRDD"]
Explanation: All six unrestricted paths are RRDD, RDRD, RDDR, DRRD, DRDR, DDRR. The four that pass through cell (1,1) are eliminated, leaving DDRR and RRDD.
Input
4 3\n2\n0 2\n2 1
Output
["DDDRR","DRRDD","RDRDD"]
Explanation: The grid requires three D moves and two R moves. Enumerating the ten possible sequences and discarding those that visit (0,2) or (2,1) leaves three valid paths: DDDRR, DRRDD, and RDRDD.
Constraints
- 1 <= m, n <= 15
- 0 <= number of obstacles < m*n
- Obstacle coordinates are within grid bounds and distinct
- The total number of valid paths fits in memory for the given limits
Optimal Approach & Strategy
Use recursive backtracking that checks bounds and obstacles before each move, building paths on the fly and pruning invalid branches immediately.
Brute Force Approach
Generate all binary strings of length m+n‑2 (right = 0, down = 1) and filter out those that step on obstacles, which is exponential and wasteful.
Code Solutions
// Backtracking solution for "Valid Grid Paths"
function findPaths(m, n, obstacles) {
const blocked = Array.from({ length: m }, () => Array(n).fill(false));
for (const [r, c] of obstacles) {
if (r >= 0 && r < m && c >= 0 && c < n) blocked[r][c] = true;
}
if (blocked[0][0] || blocked[m - 1][n - 1]) return [];
const ans = [];
const cur = [];
function backtrack(r, c) {
if (r === m - 1 && c === n - 1) {
ans.push(cur.join(''));
return;
}
// Down
if (r + 1 < m && !blocked[r + 1][c]) {
cur.push('D');
backtrack(r + 1, c);
cur.pop();
}
// Right
if (c + 1 < n && !blocked[r][c + 1]) {
cur.push('R');
backtrack(r, c + 1);
cur.pop();
}
}
backtrack(0, 0);
ans.sort(); // lexicographic (D < R)
return ans;
}
// Driver (Node.js)
const fs = require('fs');
const data = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
let pos = 0;
const m = data[pos++];
const n = data[pos++];
const k = data[pos++];
const obstacles = [];
for (let i = 0; i < k; ++i) {
const r = data[pos++];
const c = data[pos++];
obstacles.push([r, c]);
}
console.log(findPaths(m, n, obstacles).join(','));#include <bits/stdc++.h>
using namespace std;
static void backtrack(int r, int c, int m, int n, const vector<vector<bool>>& blocked,
string& cur, vector<string>& ans) {
if (r == m - 1 && c == n - 1) {
ans.push_back(cur);
return;
}
// Move Down
if (r + 1 < m && !blocked[r + 1][c]) {
cur.push_back('D');
backtrack(r + 1, c, m, n, blocked, cur, ans);
cur.pop_back();
}
// Move Right
if (c + 1 < n && !blocked[r][c + 1]) {
cur.push_back('R');
backtrack(r, c + 1, m, n, blocked, cur, ans);
cur.pop_back();
}
}
vector<string> findPaths(int m, int n, const vector<pair<int,int>>& obstacles) {
vector<vector<bool>> blocked(m, vector<bool>(n, false));
for (auto &p : obstacles) {
int r = p.first, c = p.second;
if (r >= 0 && r < m && c >= 0 && c < n)
blocked[r][c] = true;
}
// If start or end is blocked, no paths.
if (blocked[0][0] || blocked[m-1][n-1]) return {};
vector<string> ans;
string cur;
backtrack(0, 0, m, n, blocked, cur, ans);
sort(ans.begin(), ans.end()); // lexicographic order (D < R)
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int m, n; if(!(cin >> m >> n)) return 0;
int k; cin >> k;
vector<pair<int,int>> obstacles(k);
for(int i=0;i<k;++i) cin >> obstacles[i].first >> obstacles[i].second;
vector<string> paths = findPaths(m, n, obstacles);
for(size_t i=0;i<paths.size();++i){
if(i) cout << ",";
cout << paths[i];
}
cout << "\n";
return 0;
}import java.io.*;
import java.util.*;
public class Main {
// Backtracking implementation
public static List<String> findPaths(int m, int n, List<int[]> obstacles) {
boolean[][] blocked = new boolean[m][n];
for (int[] p : obstacles) {
int r = p[0], c = p[1];
if (r >= 0 && r < m && c >= 0 && c < n) blocked[r][c] = true;
}
List<String> ans = new ArrayList<>();
if (blocked[0][0] || blocked[m-1][n-1]) return ans;
StringBuilder cur = new StringBuilder();
backtrack(0, 0, m, n, blocked, cur, ans);
Collections.sort(ans); // lexicographic (D < R)
return ans;
}
private static void backtrack(int r, int c, int m, int n, boolean[][] blocked,
StringBuilder cur, List<String> ans) {
if (r == m - 1 && c == n - 1) {
ans.add(cur.toString());
return;
}
// Down
if (r + 1 < m && !blocked[r + 1][c]) {
cur.append('D');
backtrack(r + 1, c, m, n, blocked, cur, ans);
cur.deleteCharAt(cur.length() - 1);
}
// Right
if (c + 1 < n && !blocked[r][c + 1]) {
cur.append('R');
backtrack(r, c + 1, m, n, blocked, cur, ans);
cur.deleteCharAt(cur.length() - 1);
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int m = Integer.parseInt(st.nextToken());
int n = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int k = Integer.parseInt(st.nextToken());
List<int[]> obstacles = new ArrayList<>();
for (int i = 0; i < k; ++i) {
st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
obstacles.add(new int[]{r, c});
}
List<String> paths = findPaths(m, n, obstacles);
System.out.println(String.join(",", paths));
}
}import sys
def find_paths(m, n, obstacles):
"""Return all valid paths from (0,0) to (m-1,n-1) avoiding obstacles.
Each path is a string of 'D' (down) and 'R' (right)."""
blocked = [[False] * n for _ in range(m)]
for r, c in obstacles:
if 0 <= r < m and 0 <= c < n:
blocked[r][c] = True
if blocked[0][0] or blocked[m-1][n-1]:
return []
ans = []
cur = []
def backtrack(r, c):
if r == m - 1 and c == n - 1:
ans.append(''.join(cur))
return
# Down
if r + 1 < m and not blocked[r+1][c]:
cur.append('D')
backtrack(r+1, c)
cur.pop()
# Right
if c + 1 < n and not blocked[r][c+1]:
cur.append('R')
backtrack(r, c+1)
cur.pop()
backtrack(0, 0)
ans.sort() # lexicographic (D < R)
return ans
if __name__ == "__main__":
data = sys.stdin.read().strip().split()
if not data:
sys.exit(0)
it = iter(map(int, data))
m = next(it)
n = next(it)
k = next(it)
obstacles = [(next(it), next(it)) for _ in range(k)]
result = find_paths(m, n, obstacles)
print(','.join(result))// Backtracking solution for "Valid Grid Paths"
function findPaths(m, n, obstacles) {
const blocked = Array.from({ length: m }, () => Array(n).fill(false));
for (const [r, c] of obstacles) {
if (r >= 0 && r < m && c >= 0 && c < n) blocked[r][c] = true;
}
if (blocked[0][0] || blocked[m - 1][n - 1]) return [];
const ans = [];
const cur = [];
function backtrack(r, c) {
if (r === m - 1 && c === n - 1) {
ans.push(cur.join(''));
return;
}
// Down
if (r + 1 < m && !blocked[r + 1][c]) {
cur.push('D');
backtrack(r + 1, c);
cur.pop();
}
// Right
if (c + 1 < n && !blocked[r][c + 1]) {
cur.push('R');
backtrack(r, c + 1);
cur.pop();
}
}
backtrack(0, 0);
ans.sort(); // lexicographic (D < R)
return ans;
}
// Driver (Node.js)
const fs = require('fs');
const data = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
let pos = 0;
const m = data[pos++];
const n = data[pos++];
const k = data[pos++];
const obstacles = [];
for (let i = 0; i < k; ++i) {
const r = data[pos++];
const c = data[pos++];
obstacles.push([r, c]);
}
console.log(findPaths(m, n, obstacles).join(','));Asked in Top Tech Interviews
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.