Traversing 2D Grids with TypeScript: A Pathfinding Adventure

Introduction

Hello, and welcome back to our coding lesson series. In this unit, we have a fascinating problem at hand that uses the concept of 2D arrays or grids . What's interesting about this problem is that it involves not only simple traversal of the grid but also making this traversal in a unique manner. Initially, the concept might seem a bit tricky, but as we dissect the task and take it step by step, you'll surely enjoy how it unfolds. Are you ready to embark on this adventure? Let's dive right in!

Task Statement

The task before us involves the creation of a TypeScript function named pathTraverse . This function should perform a particular ordered traversal through a 2D grid. The function will accept a grid represented as a 2D array number[][], along with the starting cell coordinates as parameters. Starting from the provided cell, the function should move in any one of the four possible directions toward an adjacent cell. However, a condition governs this selection: the new cell value should be strictly greater than the current cell's value. Think of this as navigating a hiking trail where you can only move to higher ground from your current position. This pattern would continue as we keep selecting the next available larger cell value. The traversal would halt when there are no cells left that satisfy our criteria. The final result of the function will be an Array<number> that includes all the visited cell values in the order of their visitation. Consider a 3x3 grid: text 1 2 3 4 5 6 7 8 9 If we start at the cell with the value 5, we can logically move to either 6 or 8 . Let's say we choose 8; the only cell that we can now move to is 9 . After this, we have no more moves left that fit our criteria. Hence, the function returns [5, 8, 9] .

Step 1: Determine the Grid Dimensions and Possible Directions

The first thing we need to do is determine the dimensions of our grid, which is fairly straightforward in TypeScript using the length property. We can also establish the directions that our traversal can take. In the context of matrices, when we say we are moving "up," we are moving one step toward the first row (decreasing the row index). Similarly, moving "down" corresponds to moving one step toward the last row (increasing the row index), and moving left or right relates to decrementing or incrementing the column index, respectively. TypeScript function pathTraverse(grid: number[][], startRow: number, startCol: number): number[] {const rows: number = grid.length; const cols: number = grid[0].length; const directions: [number, number][] = [[-1, 0], // Up [1, 0], // Down [0, -1], // Left [0, 1] // Right]; In the directions array, each pair represents a direction in terms of a pair (rowOffset, colOffset) . So, if we are at a cell (r, c), moving up corresponds to going to the cell (r-1, c), moving down corresponds to (r+1, c), moving left corresponds to (r, c-1), and moving right corresponds to (r, c+1) .

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Step 3: Begin the Grid Traversal Process

Let's initiate the grid traversal process in our function. We first set up an infinite loop that will only stop when we break it based on a condition. Inside the infinite loop, for each iteration, we'll have the function try to select the next cell with the maximum value among the adjacent cells. If we find such a cell, we'll capture its value, and it will be our next cell.

TypeScript

function pathTraverse(grid: number[][], startRow: number, startCol: number): number[] {
    const rows: number = grid.length;
    const cols: number = grid[0].length;

    // Check the validity of the input
    if (startRow < 0 || startRow >= rows || startCol < 0 || startCol >= cols) {
        console.error("Invalid input");
        return [];
    }
    
    // Define all four possible directions of movement
    const directions: [number, number][] = [
        [1, 0], [-1, 0], [0, -1], [0, 1]
    ];

    // Start with the value at the starting cell
    const visited: number[] = [];
    visited.push(grid[startRow][startCol]);

    let currMax: number = grid[startRow][startCol];
    while (true) {
        let nextRow: number = -1, nextCol: number = -1;

        // Loop over each adjacent cell in all the directions
        for (const dir of directions) {
            // Calculate the new cell's row and column indices
            const newRow: number = startRow + dir[0];
            const newCol: number = startCol + dir[1];

            // If the new cell is out of the grid boundary, ignore it
            if (newRow < 0 || newRow >= rows || newCol < 0 || newCol >= cols) {
                continue;
            }

            // If the new cell's value is greater than the current maximum
            if (grid[newRow][newCol] > currMax) {
                // Save it as the next cell to visit
                nextRow = newRow;
                nextCol = newCol;
                currMax = grid[newRow][newCol];
            }
        }

        // Break the loop if no next cell was found
        if (nextRow === -1 && nextCol === -1) {
            break;
        }

        // Otherwise, go to the next cell
        startRow = nextRow;
        startCol = nextCol;

        // Append the cell's value to the result list
        visited.push(currMax);
    }

    // Return the list of visited cells' values    
    return visited;
}

const grid: number[][] = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
];
const result: number[] = pathTraverse(grid, 1, 1);
console.log(result); // Output should be [5, 8, 9]

function pathTraverse(grid: number[][], startRow: number, startCol: number): number[] {
    const rows: number = grid.length;
    const cols: number = grid[0].length;

    // Check the validity of the input
    if (startRow < 0 || startRow >= rows || startCol < 0 || startCol >= cols) {
        console.error("Invalid input");
        return [];
    }
    
    // Define all four possible directions of movement
    const directions: [number, number][] = [
        [1, 0], [-1, 0], [0, -1], [0, 1]
    ];

    // Start with the value at the starting cell
    const visited: number[] = [];
    visited.push(grid[startRow][startCol]);

    let currMax: number = grid[startRow][startCol];
    while (true) {
        let nextRow: number = -1, nextCol: number = -1;

        // Loop over each adjacent cell in all the directions
        for (const dir of directions) {
            // Calculate the new cell's row and column indices
            const newRow: number = startRow + dir[0];
            const newCol: number = startCol + dir[1];

            // If the new cell is out of the grid boundary, ignore it
            if (newRow < 0 || newRow >= rows || newCol < 0 || newCol >= cols) {
                continue;
            }

            // If the new cell's value is greater than the current maximum
            if (grid[newRow][newCol] > currMax) {
                // Save it as the next cell to visit
                nextRow = newRow;
                nextCol = newCol;
                currMax = grid[newRow][newCol];
            }
        }

        // Break the loop if no next cell was found
        if (nextRow === -1 && nextCol === -1) {
            break;
        }

        // Otherwise, go to the next cell
        startRow = nextRow;
        startCol = nextCol;

        // Append the cell's value to the result list
        visited.push(currMax);
    }

    // Return the list of visited cells' values    
    return visited;
}

const grid: number[][] = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
];
const result: number[] = pathTraverse(grid, 1, 1);
console.log(result); // Output should be [5, 8, 9]

Introduction

Task Statement

Step 1: Determine the Grid Dimensions and Possible Directions

Join the 1M+ learners on CodeSignal

Step 2: Validate Starting Point and Set Up Visited Cells Recording

Step 3: Begin the Grid Traversal Process

Lesson Summary