yeppe - 1 year ago 118
Java Question

# Reduced time complexity of inner loop: Find count of elements greater than current element in the first loop and store that in solved array

I want to reduce the complexity of this program and find count of elements greater than current/picked element in first loop (

`array[]`
)and store the count in solved array(
`solved[]`
) and loop through the end of the array[]. I have approached the problem using a general array based approach which turned out to have greater time complexity when 2nd loop is huge.
But If someone can suggest a better collection here in java that can reduce the complexity of this code that would also be highly appreciated.

``````for (int i = 0; i < input; i++) {
if (i < input - 1) {
count=0;
for (int j = i+1; j < input; j++) {
System.out.print((array[i])+" ");
System.out.print("> ");
System.out.print((array[j]) +""+(array[i] > array[j])+" ");
if (array[i] > array[j]) {
count++;
}
}
solved[i] = count;
}
}
for (int i = 0; i < input; i++) {
System.out.print(solved[i] + " ");
}
``````

What I want to achieve in simpler terms

Input

Say I have 4 elements in my

array[] -->86,77,15,93

output

solved[]-->2 1 0 0

2 because after 86 there are only two elements 77,15 lesser than 86

1 because after 77 there is only 15 lesser than 77

rest 15 <93 hence 0,0

There is actually a `O(n*logn)` solution, but you should use a self balancing binary search tree such as red-black tree.

Main idea of the algorithm:

You will iterate through your array from right to left and insert in the tree triples `(value, sizeOfSubtree, countOfSmaller)`. Variable `sizeOfSubtree` will indicate the size of the subtree rooted at that element, while `countOfSmaller` counts the number of elements that are smaller than this element and appear at the right side of it in the original array.

Why binary search tree? An important property of BST is that all nodes in the left subtree are smaller than the current node, and all in the right subtree are greater.

Why self-balancing tree? Because this will guarantee you `O(logn)` time complexity while inserting a new element, so for n elements in array that will give `O(n*logn)` in total.

When you insert a new element you will also calculate the value of `countOfSmaller` by counting elements that are currently in the tree and are smaller than this element - exactly what are we looking for. Upon inserting in the tree compare the new element with the existing nodes, starting with the root. Important: if the value of the new element is greater than the value of the root, it means that is also greater than all the nodes in the left subtree of root. Therefore, set `countOfSmaller` to the `sizeOfSubtree` of root's left child + 1 (because the new element is also greater than root) and proceed recursively in the right subtree. If it is smaller than root, it goes to the left subtree of root. In both cases increment `sizeOfSubtree` of root and proceed recursively. While rebalancing the tree, just update the `sizeOfSubtree` for nodes that are included in left/right rotation and that's it.

Sample code:

``````public class Test
{
static class Node {
public int value, countOfSmaller, sizeOfSubtree;
public Node left, right;
public Node(int val, int count) {
value = val;
countOfSmaller = count;
sizeOfSubtree = 1; /** You always add a new node as a leaf */
System.out.println("For element " + val + " the number of smaller elements to the right is " + count);
}
}
static Node insert(Node node, int value, int countOfSmaller)
{
if (node == null)
return new Node(value, countOfSmaller);

if (value > node.value)
node.right = insert(node.right, value, countOfSmaller + size(node.left) + 1);
else
node.left = insert(node.left, value, countOfSmaller);

node.sizeOfSubtree = size(node.left) + size(node.right) + 1;

/** Here goes the rebalancing part. In case that you plan to use AVL, you will need an additional variable that will keep the height of the subtree.
In case of red-black tree, you will need an additional variable that will indicate whether the node is red or black */

return node;
}
static int size(Node n)
{
return n == null ? 0 : n.sizeOfSubtree;
}

public static void main(String[] args)
{
int[] array = {13, 8, 4, 7, 1, 11};
Node root = insert(null, array[array.length - 1], 0);
for(int i = array.length - 2; i >= 0; i--)
insert(root, array[i], 0); /** When you introduce rebalancing, this should be root = insert(root, array[i], 0); */
}
}
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download