Question

A)Given a generic array with ‘n’ items (not only integers). Give a solution for checking whether there are any duplicate elements in the array or not? You just need to return a boolean (true or false). State the complexity of your solution. Can you come up with another solution that has O(n logn) complexity? Explain.

B) Now consider the same problem as Question A, but this time you only have positive integer numbers ranging from 0 to (n-1) in the array. Can you find a duplicate in O(n) complexity? Implement the solution.

Answer 1

public class DupTest {
    
    public static <T> boolean isDuplicates1(T arr[]) {
        
        for(int i=0; i<arr.length; i++) {
                for(int j=i+1; j<arr.length; j++) {
                        if(arr[i].equals(arr[j])) {
                                return true;
                        }
                }
        }
        
        return false;
    }
    
    public static boolean isDuplicates2(int arr[]) {
            int counts[] = new int[arr.length];
            
            for(int i=0; i<arr.length; i++) {
                    int x = arr[i];
                    
                    // If we have seen this element earlier also.
                    if(counts[x] != 0) {
                            return true;
                    }
                    
                    counts[x] += 1;
            }
            
            return false;
    }

    public static void main(String args[]) {
        System.out.println(DupTest.<Integer>isDuplicates1(new Integer[] {4, 5, 3, 6, 7, 19}));
        System.out.println(DupTest.<Integer>isDuplicates1(new Integer[] {4, 5, 3, 6, 7, 3, 19}));
        System.out.println(DupTest.isDuplicates2(new int[] {4, 5, 3, 6, 2, 1, 4}));
    }
}

**************************************************

Thanks for your question. We try our best to help you with detailed answers, But in any case, if you need any modification or have a query/issue with respect to above answer, Please ask that in the comment section. We will surely try to address your query ASAP and resolve the issue.

Please consider providing a thumbs up to this question if it helps you. by Doing that, You will help other students, who are facing similar issue.