Best of prey problem

The problem:

There are a number of animal species in the forest. Each species has one or more predator that may be direct or indirect. Species X is said to be a predator of species Y if at least or of the following is true:

• Species X is a direct predator of species Y 
• If species X is a direct predator of species Z, and Z is a direct predator of Y, then spec is an indirect predator of species Y.

Indirect predation is transitive through any numb of levels. Each species has a maximum of 1 direct predator. No two species will ever be mutual predators, and no species is a predator of itself. Your task is to determine the minimum number of groups that must be formed to so that no species is grouped with its predators, direct or indirect. As an example, consider an array where each position represents a species and each element represents a predator of that species or-1 if there are none. The array is a [-1, 8, 6, 0, 7, 3, 8, 9, -1, 6, 1] and we’ll use zero indexing. 

0              8
 \            / \
  3          1   6
   \        /   / \
    5     10   2   9
                    \
                     7
                      \
                       4
These are the trees created based on the given array.
The groups will be: [0,8], [3,1,6], [5,10,2,9], [7], [4]

We can notice that the asked number of groups without predators is, in fact, the depth of the longers tree branch. Let’s move on directly to the solutions:

O(nm)

This is a trivial solution based on two loops, therefore translating into an n^2 solution. It’s enough for the given task, as the inputs are limited to 10^3 items.

Instead of looking for the roots of a tree, we can just iterate over the array and compare the branch length in each iteration. Key is to understand that value in the item array points to the parent key i.e. given array [-1,0] it means that the element at index 0 (value -1) is the parent of the element at index 1 (value 0);

int[] ints =  {-1, 8, 6, 0, 7, 3, 8, 9, -1, 6, 1};
int max = 1;
int arrLen = ints.Length;
for (var i = 0; i < ints.Length; i++)
{
    var a = i;
    var counter = 1;
    while (ints[a] > -1 && ints[a] < arrLen && counter < arrLen)
    {
        a = ints[a];
        counter++;
    }

    if (counter > max)
        max = counter;
}
return max;

The array must contain at least one element. The counter < arrLen check is just for the case if the given array forms a cyclic graph, which would lead to an infinite loop. The time complexity of this solution is the number of items in the array times the average length of the path.

We can add a little bit of optimization by adding a hashtable tracking already calculated nodes with their corresponding depth level.

int max = 1;
int arrLen = ints.Length;
var visited = new Hashtable();
var baseLevel = 1;
for (var i = 0; i < ints.Length; i++)
{
    var a = i;
    int counter = baseLevel;

    if (visited.Contains(ints[a]))
    {
        counter = (int)visited[ints[a]]+1;
        if (counter > max)
            max = counter;
        
        visited.Add(i, counter);
        continue;
    }

    while (ints[a] > -1)
    {
        counter++;
        a = ints[a];
    }

    visited.Add(i, counter);
    if (counter > max)
        max = counter;
}

O(V+E)

We could use the depth first search algorithm with the complexity of O(V+E), however since we are not given a tree, but an array, first we’d need to build one. It’d be best to use a custom class for it, or we may use a simple implementation of tree using lists and tuples for tracking parent-children relationship.

private static List<Tuple<int, List<int>>> createTree(int[] data, List<Tuple<int, List<int>>> tree)
{
   var last = tree.Last();
   var existsParent = false;

   for (var i = 0; i < last.Item2.Count; i++)
   {
      var childrenList = new List<int>();
      for (var j = 0; j < data.Length; j++)
      {
         if (last.Item2[i] == data[j])
         {
            existsParent = true;
            childrenList.Add(j);
         }
       }
       tree.Add(new Tuple<int, List<int>>(last.Item2[i], childrenList));
    }

    if (!existsParent)
      return tree;

    return createTree(data, tree);
}

// Then use it like this

int max = 1;
int arrLen = ints.Length;
var trees = new List<Tuple<int, List<int>>>();

for (var i = 0; i < ints.Length; i++)
{
   if (ints[i] == -1)
   {
      var nodes = new List<int>();
      for (var j = 0; j < ints.Length; j++)
      {
         if (ints[j] == i)
           nodes.Add(j);
      }
      trees.Add(new Tuple<int, List<int>>(i, nodes));
    }
}

The problem with this approach is that it takes more time to build this tree, than to search it, so in the it’s time complexity is worse than the first solution.

Please let me know in comments in case you come up with a more efficient solution :).