Unique Grid Paths — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Backtracking and solve the Unique Grid Paths problem optimally.
O(m*n)O(n)Problem Description
Given an m×n matrix grid where each entry is either 0 (blocked) or 1 (free), determine how many different routes lead from the upper‑left cell (0,0) to the lower‑right cell (m‑1,n‑1). From any free cell you may move only one step down or one step right. A route is valid only if every visited cell contains 1, including the start and the destination. If either the start or the destination is blocked, the answer is 0. Return the total count as a 64‑bit integer.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Unique Grid Paths"
WHY DOES IT MATTER?
Grid‑DP with obstacles is a foundational pattern for any problem that requires counting ways under movement constraints; mastering it unlocks solutions for robot navigation, combinatorial games, and probability grids.
OPTIMIZATION CHALLENGE
The key insight is recognizing that each cell’s answer is the sum of two previously solved sub‑problems, eliminating the exponential recursion and yielding a linear‑time fill of the matrix.
REAL-WORLD CONNECTION
Think of a data‑center network where certain switches are down (blocked). Finding the number of viable packet routes from source to destination while only moving downstream mirrors this DP on a grid of operational nodes.
During an interview, sketch the DP recurrence on the whiteboard first, then mention the rolling‑array optimization to show you care about both time and space.
COMPLEXITY AT A GLANCE
O(m*n)O(n)Core Theory — Why This Approach?
The problem is a classic example of counting lattice paths with obstacles. A naïve recursive solution tries every possible sequence of down and right moves, leading to an exponential blow‑up because the same sub‑grid is recomputed many times. The underlying theory that saves us is dynamic programming: each cell’s answer depends only on the number of ways to reach the cell directly above it and the cell to its left, provided the cell itself is free. By storing these intermediate results we convert overlapping sub‑problems into a linear‑time solution. The optimal paradigm is thus a bottom‑up DP (or memoized recursion) that runs in O(m·n) time, and with a rolling‑array trick we can shrink the auxiliary space to O(n) while still preserving correctness.
Interview Questions on This Problem
Q1How do you handle the case when the start or destination cell is blocked?
Immediately return 0 because no path can begin or end on a blocked cell; this check should be performed before any DP computation.
Q2Can you reduce the space complexity from O(m·n) to O(n) and how?
Yes, by iterating row‑wise and keeping only a single 1‑D array of size n that represents the current row’s path counts, updating it in place using the relation dp[j]=grid[i][j]==1?dp[j]+dp[j-1]:0.
Q3If the answer can be very large, how would you modify the solution for a typical interview?
Compute the result modulo a large prime (e.g., 1e9+7) at each addition step to avoid overflow and satisfy constraints that ask for the answer modulo M.
Examples
Input
[[1,1,0],[1,1,1],[0,1,1]]
Output
4
Explanation: All possible sequences of two downs and two rights are examined. The sequences DDRR and RRDD hit blocked cells, while DRDR, DRRD, RDDR and RDRD stay on cells with value 1. Hence four valid routes exist.
Input
[[1,0,1],[1,1,1],[1,1,1]]
Output
3
Explanation: Using dynamic programming: first row yields dp=[1,0,0]; second row becomes [1,1,1]; third row becomes [1,2,3]. The bottom‑right cell accumulates three distinct paths.
Input
[[0,1],[1,1]]
Output
0
Explanation: The starting cell (0,0) is blocked, so no route can be formed regardless of the rest of the grid.
Constraints
- 1 <= m, n <= 100
- grid[i][j] is either 0 or 1
- The answer fits in a signed 64‑bit integer
Optimal Approach & Strategy
Use dynamic programming to fill a table where dp[i][j] = 0 if grid[i][j] is blocked else dp[i‑1][j] + dp[i][j‑1], achieving linear time.
Brute Force Approach
Recursively explore every possible down/right sequence from the start, backtracking when you hit a blocked cell, which leads to exponential time.
Code Solutions
function uniquePaths(grid) {
if (!grid.length || !grid[0].length || grid[0][0] === 0) return 0;
let m = grid.length;
let n = grid[0].length;
let dp = Array(m).fill(0).map(() => Array(n).fill(0));
dp[0][0] = grid[0][0];
for (let i = 1; i < m; ++i) {
dp[i][0] = grid[i][0] && dp[i-1][0];
}
for (let j = 1; j < n; ++j) {
dp[0][j] = grid[0][j] && dp[0][j-1];
}
for (let i = 1; i < m; ++i) {
for (let j = 1; j < n; ++j) {
if (grid[i][j] === 1) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
}
return dp[m-1][n-1];
}
let grid = [[1,1,0],[1,1,1],[0,1,1]];
console.log(uniquePaths(grid));
#include <iostream>
#include <vector>
int uniquePaths(std::vector<std::vector<int>>& grid) {
if (grid.empty() || grid[0].empty() || grid[0][0] == 0) return 0;
int m = grid.size();
int n = grid[0].size();
std::vector<std::vector<int>> dp(m, std::vector<int>(n, 0));
dp[0][0] = grid[0][0];
for (int i = 1; i < m; ++i) {
dp[i][0] = grid[i][0] && dp[i-1][0];
}
for (int j = 1; j < n; ++j) {
dp[0][j] = grid[0][j] && dp[0][j-1];
}
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
if (grid[i][j] == 1) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
}
return dp[m-1][n-1];
}
int main() {
std::vector<std::vector<int>> grid = {{1,1,0},{1,1,1},{0,1,1}};
std::cout << uniquePaths(grid) << std::endl;
return 0;
}
import java.util.*;
public class UniquePaths {
public int uniquePaths(int[][] grid) {
if (grid.length == 0 || grid[0].length == 0 || grid[0][0] == 0) return 0;
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = grid[0][0];
for (int i = 1; i < m; ++i) {
dp[i][0] = grid[i][0] == 1 && dp[i-1][0] == 1 ? 1 : 0;
}
for (int j = 1; j < n; ++j) {
dp[0][j] = grid[0][j] == 1 && dp[0][j-1] == 1 ? 1 : 0;
}
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
if (grid[i][j] == 1) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
}
return dp[m-1][n-1];
}
public static void main(String[] args) {
int[][] grid = {{1,1,0},{1,1,1},{0,1,1}};
UniquePaths uniquePaths = new UniquePaths();
System.out.println(uniquePaths.uniquePaths(grid));
}
}
def uniquePaths(grid):
if not grid or not grid[0] or grid[0][0] == 0:
return 0
m, n = len(grid), len(grid[0])
dp = [[0]*n for _ in range(m)]
dp[0][0] = grid[0][0]
for i in range(1, m):
dp[i][0] = grid[i][0] and dp[i-1][0]
for j in range(1, n):
dp[0][j] = grid[0][j] and dp[0][j-1]
for i in range(1, m):
for j in range(1, n):
if grid[i][j] == 1:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
grid = [[1,1,0],[1,1,1],[0,1,1]]
print(uniquePaths(grid))
function uniquePaths(grid) {
if (!grid.length || !grid[0].length || grid[0][0] === 0) return 0;
let m = grid.length;
let n = grid[0].length;
let dp = Array(m).fill(0).map(() => Array(n).fill(0));
dp[0][0] = grid[0][0];
for (let i = 1; i < m; ++i) {
dp[i][0] = grid[i][0] && dp[i-1][0];
}
for (let j = 1; j < n; ++j) {
dp[0][j] = grid[0][j] && dp[0][j-1];
}
for (let i = 1; i < m; ++i) {
for (let j = 1; j < n; ++j) {
if (grid[i][j] === 1) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
}
return dp[m-1][n-1];
}
let grid = [[1,1,0],[1,1,1],[0,1,1]];
console.log(uniquePaths(grid));
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.