Find duplicates in List where all the numbers in between is <= than the duplicates

My function is supposed to go through a given List and find integers of same value, but only count them if the integers between them is <= the the integers that are equal:

public static int findPairs(List arr) {
        int total = 0;

        for(int i = 0; i  arr.get(i)) ? arr.size() : j;
            }
        }
        return total;
    }

The array size can be between \$1 \le N \le 3 *10^5\$.

The numbers in the array can be between \$1 \le N \le 10^6\$.

This works, but is there any way to achieve the same thing, only a better solution performance-wise?

Firstly, note that you should use .equals not == to compare two Integer values. Also, setting j to equal arr.size() is an odd way of doing a break.

However the main problem with your algorithm is that it has worst case performance O(n^2). If you run it on a descending List like [1000000, 999999, 999998, ..., 0], it is very slow because j is never set to be arr.size().

However, for random Lists (i.e. Lists where every item is chosen using random.nextInt(1000000) for example), it is in general very quick. This is because j generally doesn't have to get very far before we break out of the j loop, so it essentially has O(n) performance for random Lists.

The fact that the performance can vary so drastically depending on the nature of the List makes it very difficult to compare two algorithms. However, for many cases the following algorithm is quicker. It only traverses the List once, keeping track of the occurrences of the numbers found. Because it uses a TreeMap I think the worst case performance is O(n log n).

private static int countPairs(List list) {
    int total = 0;
    NavigableMap map = new TreeMap<>();
    for (int a : list) {
        map.headMap(a).clear();
        Integer m = map.get(a);
        if (m == null)
            map.put(a, 1);
        else {
            map.put(a, m + 1);
            total += m;
        }
    }
    return total;
}

StackExchange Code Review Q#88804, answer score: 6