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

Question

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

Answer 1

So making the code simpler and making the code faster aren't necessarily the same thing. If you want the code to be simple and readable, you could try a sort. That is, you could try something like

int[] solved = new int[array.length];
for (int i = 0; i < array.length; i++){
    int[] afterward = Arrays.copyOfRange(array, i, array.length);
    Arrays.sort(afterward);
    solved[i] = Arrays.binarySearch(afterward, array[i]);
}

What this does it it takes a copy of the all the elements after the current index (and also including it), and then sorts that copy. Any element less than the desired element will be beforehand, and any element greater will be afterward. By finding the index of the element, you're finding the number of indices before it.

A disclaimer: There's no guarantee that this will work if duplicates are present. You have to manually check to see if there are any duplicate values, or otherwise somehow be sure you won't have any.

Edit: This algorithm runs in O(n² log n) time, where n is the size of the original list. The sort takes O(n log n), and you do it n times. The binary search is much faster than the sort (O(log n)) so it gets absorbed into the O(n log n) from the sort. It's not perfectly optimized, but the code itself is very simple, which was the goal here.

Answer 2

With Java 8 streams you could reimplement it like this:

int[] array = new int[] { 86,77,15,93 };
int[] solved =
  IntStream.range(0, array.length)
           .mapToLong((i) -> Arrays.stream(array, i + 1, array.length)
                                   .filter((x) -> x < array[i])
                                   .count())
           .mapToInt((l) -> (int) l)
           .toArray();