# The Jungle Book

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 :).

# Algorithms: Selection sort (JavaScript, PHP)

- Time complexity: O(n
^{2})

Hi, in the second episode of the algorithms series I’d like to take a closer look at yet another simple sorting technique called selection sort. Similarly to bubble sort, it consists of two dependent loops, therefore it’s time complexity also equals to O(n^{2}). It goes like this:

- While sorting the array in ascending order we set the first loop and the first element in the array as a minimum.
- We set up a second loop with a range of the second till the last element, as it doesn’t make much sense to compare the first element with itself.
- If any of the remaining elements in the array is lower than the first, we set it as a minimum.
- As a final step, the lowest value is swapped with the first value (at 0 index).
- The loop continues with j+1 element as a minimum and j+1+1 as the remaining range.

Here’s the presentation (credits to http://www.xybernetics.com):

# Algorithms: Bubble sort (JavaScript, PHP)

- Time complexity: O(n
^{2})

Bubble sort is one of the easiest sorting algorithms to implement. The name is derived from the process of sorting based on gradually “bubbling” (or rising) values to their proper location in the array. The bubble sort repeatedly compares adjacent elements of an array as in the following picture:

The first and second elements (4 and 2) are compared and swapped if out of order. Then the second and third elements (4 and 5) are compared and swapped if out of order and so on. The algorithm consists of two loops. In each iteration a single value is set in the right place. This sorting process continues until the last two elements of the array are compared and swapped if out of order (the last iteration doesn’t swap any values).