Find heap depth faster than O(n^2)

Question

Help me optimize the algorithm. I have a heap in the array. Each number in the array indicates a parent. Root is -1. I need to find the depth of heap. Example:

Array is 4 -1 4 1 1

The answer is 3.

It's my code

static int findMax(int[] mas) {
    int a[] = new int[mas.length];
    a[pos] = 1;
    int max = 0;

    for (int j = 0; j < mas.length; j++) {
        for (int i = 0; i < a.length; i++) {
            if (a[i] == 0 && a[mas[i]] != 0) {
                a[i] = a[mas[i]] + 1;
                if (a[i] > max)
                    max = a[i];
            }
        }
    }
    return max;
}

Where pos - position of root.

I also solved this problem with recursion. But tests give me "Time limit exceeded" also.

static class Node {
        static int nodesCount = 0;

        int val;
        int deep;
        List<Node> childrens = new ArrayList<>();
        static Set<Integer> deeps = new HashSet<>();

        public Node(int val, int deep) {
            this.val = val;
            this.deep = deep;
            deeps.add(deep);
            nodesCount++;
        }

        public List<Node> getChildrens() {
            return childrens;
        }

        public int getDeep() {
            return deep;
        }
    }
static int findMax(int [] mas){
    Node head = null;
    for (int i = 0; i < mas.length; i++) {
        if (mas[i] == -1)
            head = new Node(i, 1);
    }
    fillChildren(head, mas);
    return Node.deeps.stream().max(Comparator.naturalOrder()).get();
}

private static void fillChildren(Node head, int[] mas) {
    for (int i = 0; i < mas.length; i++) {
        if (mas[i] == head.val) {
            Node child = new Node(i, head.getDeep() + 1);
            head.getChildrens().add(child);
            fillChildren(child, mas);
        }
    }
}

Answer 1

To substantiate Matej's answer, here is pseudocode.

• associate a D field to every node,

• initialize all D to -1,

• from every node, follow the parent chain until your reach a node with non-negative D,

• if the root is reached, set its D to 0,

• tracing the chain backward, update the D's increasingly.

A chain traversal stops on the first non-negative node met, and all intermediate nodes become non-negative. So the negative nodes are only visited once and this justifies the O(n) behavior.

Updating all nodes in a chain is crucial, otherwise the same nodes can be visited several times. In the worst case, that could lead to O(n²) operations.

It is worth to note that the algorithm requires a stack to make the backward traversal possible. In the worst case, the stack depth can reach n, adding extra O(n) storage space (or the risk of a stack overflow is no care is taken).

A better option might be to use the D field of the traversed nodes to store the "return index" and form a temporary backward chain.

Answer 2

Remember depths of visited nodes in an array. Start traversing from first input element to its root and on backtrack store depths to visited nodes array. On each jump from child to parent check if the depth is already calculated. If yes, you don't have to go that route for second time and can use the pre-calculated value directly. Will be O(n).