LinkedHashMap complexity

Question

i have simple problem to find the first unique element in array A. But, what bothers me is the time complexity using different methods. I've tried this two methods so far.

First Method:

LinkedHashMap<Integer, List<Integer>> map = new LinkedHashMap<Integer, List<Integer>>();
for (int i = 0; i < A.length; i++)
{
    if (!map.containsKey(A[i]))
        map.put(A[i], new ArrayList<>());
    map.get(A[i]).add(i);
}

for (Map.Entry<Integer, List<Integer>> m : map.entrySet())
    if (m.getValue().size() == 1)
        return m.getKey();
return -1;

Second Method:

    for(int i=0; i< A.length; i++){
        boolean unique = true;
        nestedFor:for(int j=0; j< A.length; j++){
            if(i != j && A[i] == A[j]){
                unique = false;
                break nestedFor;
            }
        }
        if(unique)
            return A[i];
    }
    return -1;

Testing with array of 1000000 elements, the first method executes at ~2000ms, while the second at ~10ms. My question is: shouldn't the first method executes faster since its complexity is O(nLogn) compared to second method which complexity is O(n^2)? What am i missing here ? Below the test code:

    int[] n = new int[1000000];
    for (int i = 0; i < n.length; i++)
        n[i] = new Random().nextInt(2000000);

    long start = System.currentTimeMillis();
    firstUnique(n);
    System.err.println("Finished at: " + (System.currentTimeMillis() - start ) + "ms");

EDIT:

for (int i = 0; i < A.length; i++)
{
    if (!map.containsKey(A[i]))
        map.put(A[i], new ArrayList<>());
    map.get(A[i]).add(i);
}

Consumes 99% of execution time, while

for (Map.Entry<Integer, List<Integer>> m : map.entrySet())
    if (m.getValue().size() == 1)
        return m.getKey();

is always 1-3ms. So, yes filling the map is the most expensive operation.

What would you suggest as most efficient method for this kind of problem?

Answer 1

I suspect that you are not picking inputs which create "worst case" conditions for the second case.

For instance, if you construct the array such that all of the million elements have a duplicate (e.g. A[i] = 2 * i / A.length), then the second method is way, way slower than the first, since it has to check 10^12 combinations of elements.

You can make it a bit faster (roughly twice as fast) by changing the condition on the inner for loop to only check from j = i + 1, but 10^12 / 2 is still a pretty big number.

If you are simply picking random numbers to populate the array, there is a reasonable chance that the first element is unique, and a greater chance that one of the first and second elements is unique, etc. After a few elements, you'll reach near-certainty that the element is unique, so it will stop after a few iterations.

---

The 2 seconds taken for the first method is way too long. I can only think that you're not warming up your JIT correctly before the benchmark. But even without trying to do that, your first method only takes 40-50ms for me (dropping to 10-15ms after a few iterations).

Most of this time will be due to object creation - both in the autoboxing of the keys and values, and in the creation of the ArrayList instances.