Find maximum visit-able nodes in matrix

Question

I had faced this problem in a coding test and could not find an efficient approach.

Given a Matrix A, The rules for movement are as follows :

1. Can only move Right or Down from any element
2. Can only move within the same row or column of element we start from initially.
3. You can only visit or cross an element if its value is lesser than the value of element you start from.

Find total number of elements one can visit, If one starts from an element A(i,j) where i-> row and
j-> column.

Note : You have to print this output for each matrix element.

Input Matrix :
1 2 3
2 3 1
3 1 2

Output:
1 1 3
1 3 1
3 1 1

Explain : from 1 (i=0,j=0) row wise We can not traverse further so visit-able nodes = 1
Also, column wise it is same. So for (i=0,j=0) max total nodes is 1.

My approach :

Tried a normal solution where from each element we traverse right side and downward elements and find max of both visit-able element counts. But this is not efficient. Can somebody tell an efficient way to do it. Thanks in advance.

Answer 1

The key point is that we can never move past an element greater than the current element, and the values of smaller elements below or to the right of a big element is irrelevant (since when we move past the big element, we'd also be able to move past all smaller elements according to the problem statement).

• For each column, go from the bottom to the top, keeping a stack which will store elements in decreasing order, along with their index (actually we can just store the index, and use that to look up the element in the matrix).

• For each element we visit:

  • Pop elements from the stack until the largest element in the stack is greater than or equal to the current element (or it's empty).

  • The number of cells that can be visited downwards is the distance to top-most element of the stack (or all the cells to the end if the stack is empty).

  • Push that element onto the stack.

• Repeat the above process from right to left, summing the values gotten above.

• Add 1 to everything to include cells visiting themselves.

Since we only do a constant amount of work per cell, the complexity here is O(rows*columns).

Java code for this:

int[][] array = {{1, 2, 3},
                 {2, 3, 1},
                 {3, 1, 2}};
Stack<Integer> stack = new Stack<Integer>(); // stores the index only
int[][] output = new int[array.length][array[0].length];
for (int i = array.length-1; i >= 0; i--) // direction not important
{
    stack.clear();
    for (int j = array[0].length-1; j >= 0; j--)
    {
        while (!stack.empty() && array[i][stack.peek()] < array[i][j])
            stack.pop();
        int offset;
        if (stack.empty())
            offset = array[0].length;
        else
            offset = stack.peek();
        output[i][j] = offset - j - 1;
        stack.push(j);
    }
}

// same as above, just with indices swapped
for (int i = array[0].length-1; i >= 0; i--) // direction not important
{
    stack.clear();
    for (int j = array.length-1; j >= 0; j--)
    {
        while (!stack.empty() && array[stack.peek()][i] < array[j][i])
            stack.pop();
        int offset;
        if (stack.empty())
            offset = array.length;
        else
            offset = stack.peek();
        output[j][i] += offset - j - 1;
        stack.push(j);
    }
}

for (int i = 0; i < array.length; i++)
for (int j = 0; j < array[0].length; j++)
    output[i][j] += 1;

for (int[] a: output)
    System.out.println(Arrays.toString(a));

Live demo.

Answer 2

I think one way to optimize your code is by making use of caching, here is one small implementation of the algorithm.

    int visited[3][3];
    memset(visited, -1, sizeof(visited));

    int calculateMaxVisitedNode(int x, int y, int visit_count, int r, int c, int valx, int valy)
    {
        if(x>r || y>c)
        {
            return visit_count;
        }
        if(visited[x][y] != -1)
        {
            return visited[x][y];
        }

        int right = 0;
        int down = 0;

        if(A[valx][valy] > A[x][y+1])
        {
            right = f(x,y+1,visit_count+1,r,c,valx,valy);
        }

        if(A[valx][valy] > A[x+1][y])
        {
            down = f(x+1,y,visit_count+1,r,c,valx,valy);
        }

        visited[x][y] = max(right, down);
        return visited[x][y];
    }

So here I am caching already visited cells, so no need to traverse through them again. This could reduce your time complexity by significant amount when number of rows and columns are very high.