Java, First Duplicate value from an array in O(n) 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) because of contains check inside the for loop.

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

Implementation of .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;
    }

contains() method for HashSet [runs in O(1)](https://stackoverflow.com/questions/25247854/hashset-contains-performance) . So your code is already O(n). — acnn, Oct 25 '17 at 14:02
@luk2302 When I look at the code of .contains, it has a for loop iterating over n. So the complexity should be O(n). Correct me if I am wrong. I have update the question with .contains code of java — , Oct 25 '17 at 14:02
You have already been corrected by @acnn . Not every loop is O(n): `for(int i = 0; i < n; i++) { return; }` — luk2302, Oct 25 '17 at 14:04
You are checking the `contains` of `ArrayList` which is completely irrelevant here since the object you call `contains` on is a `HashSet`. — luk2302, Oct 25 '17 at 14:06
@acnn `contains()` for HashSet doesn't always run in O(1). It depends on the hash function and the data. In the worst case, it can run in O(n). — Malt, Oct 25 '17 at 14:07
@luk2302 okay, so if it is a list, then list.contains complexity is O(n). Am I correct? — , Oct 25 '17 at 14:07
Borrowing the idea of counting sort, you could create a `temp` array for storing the number of `a[i]` occurrences in a `temp[a[i]]`. If a `temp[a[i]]` is greater than `0`, `a[i]` is the answer. Otherwise, increment a `temp[a[i]]` and proceed to the next element. — Andrew Tobilko, Oct 25 '17 at 14:07
@AndrewTobilko what size does `temp` have? 2,147,483,647 ? What about the negative contents of `a`? — luk2302, Oct 25 '17 at 14:09
@luk2302, right, it would be working for a small range, that's why I asked about the range. — Andrew Tobilko, Oct 25 '17 at 14:11

score 3 · Answer 1 · answered Oct 25 '17 at 14:12

The implementation you're providing corresponds to the contains(Object) method in the ArrayList class. The method you're using is actually HashSet.contains(Object).

The complexity of HashSet.contains(Object) is O(1). To achieve this, it uses a hash of the value stored to find the element searched for.

In the unlikely event that two objects share the same hash, both elements will be stored under the same hash in a list. This might be the reason that is misleading you to believe that the cost for HashSet.contains(Object) is O(n). Although there is a list, elements are nearly evenly distributed, and thus the list size tends to 1, transforming O(n) to O(1).

score 2 · Answer 2 · answered Oct 25 '17 at 15:15

As already explained in this answer your algorithm has already O(n) time complexity as HashSet’s lookup methods (includes both contains and add) have O(1) time complexity.

Still, you can improve your method, as there as no reason to perform two lookups for each element:

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

The contract of Set.add is to only add a value (and return true) if the value is not already contained in the set and return false if it is already contained in the set.

Using this you may end up with half the execution time (it’s still the same time complexity) and have simpler code…

Mike · Answer 3 · 2017-10-25T15:31:04.390

-5

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;
            }
        }         
}

edited Oct 25 '17 at 15:31

answered Oct 25 '17 at 14:21

Mike

512
3
16

this is a java function you have to make a call in your main function for example firstDuplicate({1,2,2,3,4}, 5) – Mike Oct 25 '17 at 15:04
1

I think he rather wanted to know how the method itself solves the issue. What is the trick? Can you explain or comment it? Just posting some lines of codes often isn't that helpful, especially for beginners. Instead post an explanation together with it. – Zabuzard Oct 25 '17 at 15:18
2

This doesn’t look like Java code, but rather like C code, e.g. Java doesn’t need the array length as parameter and there’s no top level `printf` function. In C, it may also happen to work with buffer overflows staying unnoticed, e.g. if you call `firstDuplicate({10, 1, 10 }, 3)`. Further, you forgot to place curly braces around the `else` block, indentation alone is not enough. Your code does `break` after the first element unconditionally (if not the first element already cause an `ArrayIndexOutOfBoundsException`)… – Holger Oct 25 '17 at 15:23
traverse the list for i= 0 to n-1 elements { check for sign of A[abs(A[i])] ; if positive then make it negative by A[abs(A[i])]=-A[abs(A[i])]; else // i.e., A[abs(A[i])] is negative this element (ith element of list) is a repetition so exit for loop } @ole V.V : I hope this might help you. Please mark the as answered if this has worked for you as you needed – Mike Oct 25 '17 at 15:24
3

I’m far from convinced it works correctly. If the array contains 1 and -1, will it be reported a duplicate since your are taking `abs()`? If the array has length 5 and contains a 7, will it crash with an exception? – Ole V.V. Oct 25 '17 at 17:16

Java, First Duplicate value from an array in O(n) time complexity

3 Answers3