Question

Given an array A of integers, -100,000 <= A[i] <= 100,000, 1 <= 10,000 (n = size of array), some elements appear multiple times and others appear once.

write a function that returns all the elements that appear multiple times in this array. (solution should be O(n) or faster)

public static List<Integer> find duplicates (List<Integer> nums) {

}

Answer 1

//do comment if any problem arises

This is the required function

public static List<Integer> find_duplicates(List<Integer> nums) {

        // create a temporary array named occurences which holds how many times a number

        // has occured

        // for -1 we add 100000 to it then increement occurences

        // for -100000 we add 100000 which is 0 then add 1 to it

        int[] occurences = new int[200001];

        for (int i = 0; i < nums.size(); i++) {

            occurences[nums.get(i) + 100000]++;

        }

        // list to return

        List<Integer> ret = new ArrayList<Integer>();

        // for all values in occurences which are greater than 1 add that value to ret

        for (int i = 0; i < 200001; i++) {

            if (occurences[i] > 1) {

                ret.add(i - 100000);

            }

        }

        return ret;

    }

Time complexity of this algorithm is O(n) as nums list is traversed only once.