Recently I’ve found an interesting problem on HackerRank:

There are a number of animal species in the jungle. 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 :).

  • Zar Shardan

    // C# O(n) solution. Enjoy.
    void Main()
    {
    var l = new List {-1, 8, 6, 0, 7, 3, 8, 9, -1, 6, 1};
    Console.WriteLine(GetTreeHeight(l));
    }
    //O(n)
    static int GetTreeHeight(List nodes)
    {
    var dt = new DepthTracker(nodes);

    return dt.GetHeight()+1;
    }

    class DepthTracker{
    List Nodes;
    int[] Depth;

    //O(n)
    public DepthTracker(List nodes){
    Nodes = nodes;
    Depth = new int[Nodes.Count];

    for (var i = 0; i -1 && Depth[i] == 0)
    {
    Depth[i] = CheckDepth(i);
    }
    }
    }

    // Count number of hops from this node to the root, update depth for every node visited
    // O(1) amortized, O(n) worst case
    public int CheckDepth(int index)
    {
    if(index == -1) return 0; // never really happens
    if(Depth[index] > 0)
    return Depth[index]; // already calculated

    var nextIdx = Nodes[index];
    if(nextIdx == -1) //this is a root node
    {
    Depth[index] = 0;
    return 0;
    }
    // might want to convert this to iterative solution + stack to prevent SOF on really large inputs,
    // but can’t be bothered right now.
    var thisDepth = CheckDepth(nextIdx) + 1;

    Depth[index] = thisDepth;
    return thisDepth;
    }

    // O(n)
    public int GetHeight() => Depth.Max();
    }

  • Zar Shardan

    It butchered the code.

    Check here instead: https://dotnetfiddle.net/ZtQYdh

    • pawel.p

      Great, well done, really like the solution! 🙂

  • Anon

    Can you post link to that question?

    • pawel.p

      Hi, unfortunately, the problem is not available publicly, I received it when applying to a .NET engineer position.

  • Coderx

    If we make a graph via adjacency matrix then we just have to a dfs so complexity will be O(V)+O(v+E).Correct If I am wrong somewhere code is attached below.
    #include
    #define ll long long int
    using namespace std;

    ll ans;
    void dfs(vector<vector>&adj,ll u,ll ht){
    ans=max(ans,ht);
    for(auto x:adj[u]){
    dfs(adj,x,ht+1);
    }
    }
    int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll t,n;
    cin>>t;
    while(t–){
    cin>>n;
    vectorvec(n);
    vector<vector>adj(n);
    vectorroot;
    for(ll i=0;i>vec[i];
    if(vec[i]==-1){
    root.push_back(i);
    }
    else{
    adj[vec[i]].push_back(i);
    }
    }
    ans=0;
    for(ll i=0;i<root.size();i++){
    dfs(adj,root[i],1);
    }
    cout<<ans<<endl;
    }

    }

This site uses Akismet to reduce spam. Learn how your comment data is processed.