Finding all integers in an array with odd occurrence I am doing an interview exercise problem from here.

The problem is to find "all numbers that occurred an odd-number of times in an array".

Here is my high level psuedo code thinking:


Construct a map that will map integers to their frequencies.
Iterate through the array, use the map to record the frequency count.
Iterate through all the keys in the map and add the keys that have an odd value to another collection.
Convert that collection to an array and return it to the user.


Here is the my implementation of this high level psuedo code in Java:

public static int[] allOdd(int[] array) {
    Map&lt;Integer, Integer&gt; hm = new HashMap&lt;Integer, Integer&gt;();
    for(int c=0;c&lt;array.length;c++) {
        if(hm.containsKey(array[c])) {
            hm.put(array[c], hm.get(array[c]) + 1);
        } else {
            hm.put(array[c], 1);
        }
    }
    List&lt;Integer&gt; allOdds = new ArrayList&lt;Integer&gt;();
    for(int key: hm.keySet()) {
        if(hm.get(key) % 2 == 1) {
            allOdds.add(key);
        }
    }
    int[] allOs = new int[allOdds.size()];
    for(int c=0;c&lt;allOdds.size();c ++){
        allOs[c] = allOdds.get(c);
    }
    return allOs;
}


I tested this for two of my test cases and in both test cases ( {2,3,2,4,4,4,6,8,8} and {90,91,91,93,93,93,95,98,98,97} ), this function produced the right results([3, 4, 6] and [97, 93, 95, 90] respectively).

Is there anything I can do to improve the time and space complexity of this method. One of the worries I had was that I created too many collections (too much space) But to me each collection had its own purpose. The map was to map values to frequencies. The ArrayList was a dynamic structure to hold the odd occurrences. You needed to initialize the last array because ArrayList is a collection that holds objects so you need to manually iterate through the ArrayList and store those ints (Auto box) in the new array. To Array

Is there anything you can point out that can improve time and space efficiency in this function?
You don't really need to keep track of how many times you've seen each integer, only whether you've seen it an odd number of times. So start with your data structure (map, hash table, dictionary, whatever) being empty, which correctly reflects the state that you have seen no numbers an odd number of times. Now for each number x in the array, if x is in the map then remove it (now you've seen it an even number of times) otherwise add it.