Demo: Chaos in the Grid (Bottom-Up)

In this assignment, we'll do a walkthrough of another DP problem, "Chaos in the Grid". We'll start with the bottom-up approach this time to mix it up a bit.

Problem Description

// You are given a grid represented as a nested array filled
// with empty strings. Chaos, the puppy, is standing at the
// top-left corner of the grid and can move either down or right
// at any point in time. Determine the number of distinct paths
// Chaos can take to reach a bowl of treats placed at the
// bottom-right corner of the grid.

// Define a function `chaosInTheGrid` that, given a nested
// array, returns the number of unique paths that Chaos
// can take to reach the bottom-right corner.

// The grid will have at least 1 row and 1 column.

// Example:

// Given the following 2x3 grid:

const grid = [
  ["", "", ""],
  ["", "", ""],
];

// There are three distinct path Chaos can take:
// 1. Right -> Right -> Down
// 2. Right -> Down -> Right
// 3. Down -> Right -> Right

function chaosInTheGrid(grid) {
  // implementation
}

// Test cases

const grid1 = [[""]];
const grid2 = [
  ["", ""],
  ["", ""],
];
const grid3 = [
  ["", "", ""],
  ["", "", ""],
  ["", "", ""],
];
const grid4 = [
  ["", "", "", "", ""],
  ["", "", "", "", ""],
  ["", "", "", "", ""],
];
const grid5 = [
  ["", "", "", "", "", ""],
  ["", "", "", "", "", ""],
  ["", "", "", "", "", ""],
  ["", "", "", "", "", ""],
  ["", "", "", "", "", ""],
  ["", "", "", "", "", ""],
];
console.log(chaosInTheGrid(grid1) === 1);
console.log(chaosInTheGrid(grid2) === 2);
console.log(chaosInTheGrid(grid3) === 6);
console.log(chaosInTheGrid(grid4) === 15);
console.log(chaosInTheGrid(grid5) === 252);
// All test cases should log true

Bottom-Up Walkthrough

We'll use the grid below to explain the problem.

Each number to the left of the square corresponds to the appropriate subarray index: 0 is the first row, 1 is the second row, etc. Each number at the top of the square corresponds to the array index within a subarray and represents a column: 0 is the first column, 1 is the second column, etc. Chaos can only move down or right.

In the bottom-up approach, we start with the simplest case (the smallest subproblem) and build up the solution iteratively.

So let's think about it: What is the smallest possible subproblem? In other words, where does Chaos start?

Chaos starts from the top-left corner, square (0, 0). Once again, we are using 0 as the first row and column index since arrays use 0-based indexing. How many unique paths are there to get to square (0, 0)?

The answer is simple: only one. Since we are already standing there, there is only one way to get there.

Now let's look at square (0, 1), which is the first row, but the second column. How many distinct paths are there for Chaos to get to that square? Still, one, because it can only come from the left.

What about square (0, 2)? Once again, there is only one path. It's important to note that we are not counting the number of steps Chaos takes; it's clear that from the initial square, Chaos needs to take two steps to get to square (0, 2). However, even though Chaos takes two steps, it is still only one path: right -> right.

What if we started going down from the initial square? In how many distinct ways can Chaos reach square (1, 0)? The answer is, you've guessed it, one. Chaos can only move down to get to that square.

What this means for us is that we can fill in the entire first row and column with 1s initially, as there is only one way to get to the bottom of the first column (by going down -> down -> down...) or to the far right of the first row (by going right -> right -> right...).

This is our starting point. Now let's look at square (1, 1). Chaos can move right -> down or down -> right. These are two distinct paths. One path leads from the top (red path), and the other path leads from the left (purple path).

Now let's check the square (1, 2), the second row, third column. How many paths are there to get to that one?

There are 3 different paths to get to square (1, 2):

1. right -> right -> down (red path)
2. right -> down -> right (blue path)
3. down -> right -> right (purple path).

What we can see is that one path leads from the top, and two paths lead from the left. We also see that the number at the top is 1 and the number to the left is 2. If we sum these two numbers, we get 3, which is the total number of paths to get to square (1, 2).

We could keep examining squares, but at this point we can start to see a pattern. The number of paths to get to any particular square is the sum of the paths to get to the square above it plus the number of paths to get to the square to the left of it. It's important to note that this only works because we know that Chaos may only move right or down. Put another way, Chaos may only approach a square from the top or left.

Let's walk through an example.

One final thing we haven't discussed is what data structure we would use for a DP object. Since we are dealing with a grid (nested array), a nested array seems appropriate as a DP object as well.

---

Let's use a simple 3x3 grid.

Step 1: First, we'll fill in the first row and column with 1s. The first row is the first nested subarray, and the first column consists of the first elements in each subarray, as you can see visually.

Step 2: Next, we'll start iterating through the grid, row by row, and fill in each square by summing the values from the top and left. The first square to consider is (1, 1), and its value will be 2.

Step 3: The final square in the second row is (1, 2), and we calculate its value to be 3.

Step 4: In the third row, the first square is (2, 1), and its value is the sum of the value from the top, 2, and the value from the left, 1, which equals 3.

Step 5: In the final step, the first square is (2, 2), and its value is the sum of the value from the top, 3, and the value from the left, 3, which equals 6. This is our result.

---

Solution

Let's see the code implementation:

function chaosInTheGrid(grid) {
  const rows = grid.length;
  const cols = grid[0].length;

  // Populate every square in the first row with 1s
  for (let col = 0; col < cols; col++) {
    grid[0][col] = 1;
  }

  // Populate every square in the first column with 1s
    for (let row = 0; row < rows; row++) {
    grid[row][0] = 1;
  }

  // Iterate over each square that isn't in the first row or column
  for (let row = 1; row < rows; row++) {
    for (let col = 1; col < cols; col++) {
      // Populate the current square with the sum of the values
      // in the squares above it and to the left of it
      grid[row][col] = grid[row - 1][col] + grid[row][col - 1];
    }
  }

  return grid[rows - 1][cols - 1];
}