Grid Unique Paths 🎯

Welcome to our comprehensive guide on Grid Unique Paths! In this lesson, we'll explore how to calculate the number of unique paths in a grid, a common problem in Data Structures and Algorithms. Let's dive in!

Introduction 📝

In this tutorial, we'll learn about the Grid Unique Paths Problem, where we're given an m x n grid with obstacles (represented by 1) and safe paths (represented by 0). The goal is to find the number of unique paths from the top-left corner of the grid ((0, 0)) to the bottom-right corner ((m-1, n-1)).

The Concept 💡

To solve the Grid Unique Paths Problem, we'll use Dynamic Programming. This approach allows us to break down complex problems into smaller, more manageable subproblems, solving each one only once.

Understanding the Dynamic Programming Approach

Base Cases: Find the number of unique paths for the smallest possible subproblems (i.e., subgrids with only one cell).
Recursive Formula: Develop a formula that combines the solutions to smaller subproblems to solve the current problem.
Memoization: Store the solutions to previously solved subproblems to avoid unnecessary redundant computations.

Implementing the Solution 💻

Now, let's implement the Dynamic Programming solution for the Grid Unique Paths Problem. We'll create a function called uniquePaths(obstaclesGrid) that accepts a 2D array (obstaclesGrid) representing the grid with obstacles and safe paths.

javascript

function uniquePaths(obstaclesGrid) {
  // m and n are the dimensions of the grid
  const m = obstaclesGrid.length;
  const n = obstaclesGrid[0].length;

  // Create a dp array to store the number of unique paths for each subgrid
  const dp = new Array(m)
    .fill(0)
    .map(() => new Array(n).fill(0));

  // The base cases are the subgrids with only one cell
  dp[0][0] = 1; // If the subgrid has only one cell and it's safe, there's one unique path

  // Recursive formula: dp[i][j] is the number of unique paths to reach the cell (i, j)
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (obstaclesGrid[i][j] === 1) continue; // Skip obstacles

      // If the current cell is safe, we can reach it from the cell above and to the left
      // (If either cell is an obstacle, there's no unique path to reach the current cell)
      if (i > 0) dp[i][j] += dp[i - 1][j];
      if (j > 0) dp[i][j] += dp[i][j - 1];
    }
  }

  // The number of unique paths to reach the bottom-right corner is the value in the last row and column of dp
  return dp[m - 1][n - 1];
}

💡 Pro Tip: Memoization can be used to optimize the solution if the grid is large.

Testing the Solution ✅

Now that we've implemented our solution, let's test it with some examples!

javascript

const obstaclesGrid1 = [
  [0, 0, 0],
  [0, 1, 0],
  [0, 0, 0]
];
console.log(uniquePaths(obstaclesGrid1)); // Output: 2

const obstaclesGrid2 = [
  [0, 0, 0, 0],
  [0, 1, 0, 0],
  [0, 0, 0, 0],
  [0, 0, 0, 0]
];
console.log(uniquePaths(obstaclesGrid2)); // Output: 1

Conclusion 📝

In this tutorial, we learned how to solve the Grid Unique Paths Problem using Dynamic Programming. We discussed the problem statement, the Dynamic Programming approach, and implemented a solution in JavaScript.

Now that you understand the concept, try solving the following quiz to reinforce your knowledge: