Finding the duplicates in the array

Question

So here is this function that has 2 arguments given that is the array and the size of array and we have to return the answer in form of Arraylist. I wrote this code but it was giving me time limit exceeded error and I was solving this as a problem on geeksforgeeks but I am not getting why is it giving time limit exceeded error. Thank you!

public static ArrayList<Integer> duplicates(int arr[], int n) {
    Arraylist<Integer> arrList = new ArrayList<>();
    Arrays.sort(arr);
          
    for(int i=0; i<n; i++) {
        if(arr[i] == arr[i+1] && !arrList.contains(arr[i])) {
            arrList.add(arr[i]);
        }
    }
    
    if(arrList.isEmpty()) {
        arrList.add(-1);
    }
    
    return arrList;
}

`arr[i] == arr[i+1]` will probably through an arrayOutOfBoundsException — Scary Wombat, Sep 08 '22 at 04:21

Badri Paudel · Answer 1 · 2022-09-08T07:53:23.597

You don't need sort as sorting has higher complexity O(nlog(n)). Not sure what are the constraints and instructions for this question, but if you really don't have problem using extra space, you can use another array list, navigate through all the elements in the arr and put it to the some list called temp and check if number is already in the temp . Code reference is given below :

    List<Integer> result = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();
    int n = arr.length; // or you already passed n
    for(int i=0;i<n;i++){
        if(!temp.contains(arr[i])) {
            temp.add(arr[i]);
        }
        else {
            result.add(arr[i]);
        }
    }
   return result;

This will be done at O(n) for both time and space complexity. Of course, if you want to achieve the result without using extra space, you've to use another approach.

score 0 · Answer 2 · answered Sep 08 '22 at 07:47

I think expected time complexity to solve this problem is o(n) but you used sorting that's why its time complexity is o(nlogn). so you can use Treemap (which stores values in sorted order) to solve this problem in o(n) time complexity.

    class Solution {
    public static ArrayList<Integer> duplicates(int arr[], int n) {
        TreeMap <Integer,Integer> map= new TreeMap<>();
        ArrayList <Integer> ans= new ArrayList<>();
        
        for(int i=0;i<n;i++){
            map.put(arr[i],map.getOrDefault(arr[i],0)+1);
        }
        
        for(int key : map.keySet()){
            if(map.get(key)>1){
                ans.add(key);
            }
        }
        if (ans.size()==0){
            ans.add(-1);
            return  ans;
        }
        
        return ans;
    }
}

`in o(n) time complexity` - that's **not** correct. Remember as the rule of thumb that maintain a sorted data structure has a cost. `TreeMap` is based on a [Red-black tree](https://en.wikipedia.org/wiki/Red%E2%80%93black_tree). Adding a new element has a logarithmic time complexity. And you're paying this cost second time while using `get()` (it also runs in **O(log n)**). That gives linear-logarithmic **O(n*log n)** overall time complexity, not linear. — Alexander Ivanchenko, Sep 08 '22 at 09:25

Alexander Ivanchenko · Answer 3 · 2022-09-08T08:14:08.410

Condition arr[i] == arr[i+1] would cause an exception during the last iteration step (when i=n-1) with 100% certainty because i+1 will refer to the index that doesn't exist. You need to get rid of it.

contains() check on a List is expensive, it has O(n) time complexity. Which results in the overall quadratic O(n^2) time complexity of your solution.

As @Scary Wombat has pointed out in the comment, you can use HashSet to check whether the element was previously encountered or not. It would also eliminate the need for sorting the data and time complexity of the solution would be linear O(n).

In case if you have a requirement the result should be sorted, then it'll be more efficient to sort the resulting list (because it would contain fewer data than the given array).

public static List<Integer> duplicates(int[] arr, int n) {
    Set<Integer> seen = new HashSet<>();
    List<Integer> duplicates = new ArrayList<>();
    
    for (int i = 0; i < n; i++) {
        int next = arr[i];
        if (!seen.add(next)) {
            duplicates.add(next);
        }
    }
        
    if (duplicates.isEmpty()) {
        duplicates.add(-1);
    }
        
//    duplicates.sort(null); // uncomment this Line ONLY if results required to be in sorted order
        
    return duplicates;
}

Sidenotes:

Don't use concrete classes like ArrayList as a return type, type of variable, method parameter, etc. Leverage abstractions, write the code against interfaces like List, Set, etc. If coding platform wants you to return an ArrayList, that unfortunate - leave the type as is, but keep in mind that it's not the way to go. See What does it mean to "program to an interface"?
Avoid using C-style of array declaration int arr[]. Because it mixes the variable name and the type, which might look confusing. int[] arr is preferable.

Finding the duplicates in the array

3 Answers3