Java, The first duplicate value from an array in O (n) of time complexity

Question

int firstDuplicate(int[] a) {
    Set<Integer> result = new HashSet();
    for(int i=0; i<a.length; i++) {
        if(result.contains(a[i])) {
            return a[i];
        } else {
            result.add(a[i]);
        }
    }
    return -1;
}

The complexity of the above code is O(n2)due to the presence of validation inside the for loop.

How to achieve this with complexity O(n)in java.

Executing .contains for ArrayList

public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

Answer 1

The following is the implementation of hashset. Whatever you say in this question is an implementation of list.contains.

For list.contains, complexity is O (n), and for a Hash set, it's O (1)

final Node<K,V> getNode(int hash, Object key) {
            Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
            if ((tab = table) != null && (n = tab.length) > 0 &&
                (first = tab[(n - 1) & hash]) != null) {
                if (first.hash == hash && // always check first node
                    ((k = first.key) == key || (key != null && key.equals(k))))
                    return first;
                if ((e = first.next) != null) {
                    if (first instanceof TreeNode)
                        return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            return e;
                    } while ((e = e.next) != null);
                }
            }
            return null;
        }

Answer 2

The implementation you provide corresponds to the method contains(Object)in the class ArrayList. The method you use is actually HashSet.contains (Object) .

HashSet.contains(Object) O (1). , , .

, , . , , , HashSet.contains(Object) O (n). , , , , 1, O (n) O (1).

Answer 3

, O(n) HashSet s ( contains, add) O(1) .

, , :

static int firstDuplicate(int[] a) {
    Set<Integer> result = new HashSet<>();
    for(int i: a) if(!result.add(i)) return i;
    return -1;
}

The contract Set.addis only to add a value (and return true) if the value is not already in the set and returns falseif it is already in the set.

Using this, you can get half the runtime (its still time complexity) and have simpler code ...

Answer 4

void printRepeating(int a[], int asize){
        int i;  
        System.out.println("The repeating elements are : ");    
        for (i = 0; i < asize; i++)
        {
            if (a[Math.abs(a[i])] >= 0){
                a[Math.abs(a[i])] = -a[Math.abs(a[i])];
            }
            else{
                System.out.print(Math.abs(a[i]) + " ");
                break;
            }
        }         
}