Struggling with an increasing paths algorithm question

Question

I’m struggling to find a good solution to a problem which asks for ALL paths which increase as you traverse a 2D array/matrix (rather than the classic ‘Longest Increasing Path’.

Here’s the question:

Definitions 
• Path: a sequence of two or mere spaces for which ea. space is horizontally or vertically adjacent to the previous 
• Increasing path: a path for which each space has a greater value than the previous space. 

Example 1: 
[
   [5, 1],
   [2, 7]
]

There are 4 Increasing paths.
1 -> 5
1 -> 7
2 -> 5
2 -> 7

Example 2: 
[
   [0, 4, 3],
   [5, 8, 9],
   [5, 9, 9]
]

There are 4 Increasing paths.
0 -> 4
0 -> 4 -> 8
0 -> 4 -> 8
0 -> 4 -> 8 -> 9 
0 -> 5 
0 -> 5 -> 8
... and so on. 

I’ve tried a few things, but none of which what I need. Because I don’t want this to seem like an “answer my homework for me”, here’s the code of what I’ve tried (I knew it wouldn’t work 100%, but it was a good start for me, and I wasn’t sure where to go from there)

/* 
   This attempt was from what I 
   gathered from longest increasing,
   so it clearly isn’t valid. 
*/ 

function(v){
        let n=v.length;
        let m=v[0].length;
        let mem=(new Array(n));
        for(let i=0;i<n;i++)mem[i]=(new Array(m)).fill(0);
        mem[0][0]=1;
        for(let i=1;i<n;i++){
            if (v[i][0] > v[i-1][0] && mem[i-1][0] == 1) {
                mem[i][0] = 1;
            }
        }
        for(let i=1;i<m;i++){
            if (v[0][i] > v[0][i-1] && mem[0][i-1] == 1) {
                mem[0][i] = 1;
            }
        }
        
        for(let i=1;i<n;i++){
            for(let j=1;j<m;j++){
                if (v[i][j] > v[i-1][j] && mem[i-1][j] == 1) {
                    mem[i][j] = 1;
                }
                if (mem[i][j] == 0 && v[i][j] > v[i][j-1] && mem[i][j-1] == 1){
                    mem[i][j] = 1;
                }
            }
        }
        return mem[n-1][m-1] ? n+m-1 : -1;
    }

(Note: I come from a strictly UX and front-end background, but I’m trying to improve my skills on this type of programming and move to a more full stack position, so I appreciate the help with a novice question! :))

Answer 1

The following is the way I have solved using Javascript

const savedPathCount = [];

function getAvailablePath(grid, x, y) {

    if (!savedPathCount[x]) {
        savedPathCount[x] = [];
    }

    if (savedPathCount[x][y]) {
        return savedPathCount[x][y]
    }

    savedPathCount[x][y] = 0

    const currentValue = grid[x][y];

    if (y > 0) {
        const topValue = grid[x][y - 1];
        if (topValue && topValue > currentValue) {
            savedPathCount[x][y]++;
            savedPathCount[x][y] += getAvailablePath(grid, x, y - 1)
        }
    }

    if (x > 0) {
        const leftValue = grid[x - 1][y];
        if (leftValue && leftValue > currentValue) {
            savedPathCount[x][y]++;
            savedPathCount[x][y] += getAvailablePath(grid, x - 1, y)
        }
    }

    if (grid[x]) {
        const rightValue = grid[x][y + 1];
        if (rightValue && rightValue > currentValue) {
            savedPathCount[x][y]++;
            savedPathCount[x][y] += getAvailablePath(grid, x, y + 1)
        }
    }

    if (grid[x + 1]) {
        const bottomValue = grid[x + 1][y];
        if (bottomValue && bottomValue > currentValue) {
            savedPathCount[x][y]++;
            savedPathCount[x][y] += getAvailablePath(grid, x + 1, y)
        }
    }

    return savedPathCount[x][y];
}

function paths(grid) {
    // Write your code here
    let pathCount = 0
    for (let x = 0; x < grid.length; x++) {

        for (let y = 0; y < grid[x].length; y++) {
            pathCount += getAvailablePath(grid, x, y);
        }
    }
    return pathCount;
}

const grid = [[15, 34],[1, 6]]

console.log(grid(path))

Answer 2

Some tips:

View the grid as a graph, nodes are each gridpoint and edges are formed where it is possible to move from a to b

An increasing path means going from a smaller value a to a bigger value b.

• This ensures that the graph is directed. (you can never go back the same edge)
• such a path a->b->c...->f you can never connect to any earlier point in your path, as it would imply that a < b < .. < f < a. this means that the graph has no cycles

A graph with directed edges and no cycles are known as DAGs (directed acyclic graphs). Many graph algorithms are a lot easier on these graphs, including listing all paths.

Your task is simply to write a DFS (depth first search) and start it on every gridpoint (filter out path of length 0 in the end).