-3

My Solution:

public class removeUniqueElements {
    public static Integer[] removeUnique(int[] arr){
        Map<Integer,Integer> output = new HashMap<Integer,Integer>();
        List<Integer> result = new ArrayList<Integer>();
        for(int i=0;i<arr.length;i++){
            if(output.containsKey(arr[i])){
                int count = output.get(arr[i]);
                count = count+1;
                output.put(arr[i],count);
            }
            else
            {
                output.put(arr[i],1);
            }
        }
        for(int i=0;i<arr.length;i++){
            if(output.get(arr[i])!=1){
                result.add(arr[i]);
            }
        }
        return result.toArray(new Integer[result.size()]);
    }

    public static void main(String[] args){
        int[] array = {1,2,3,4,2,3,4};
        Integer[] result = removeUnique(array);
        System.out.println(Arrays.toString(result));
    }
}

Time Complexity : O(n) Space Complexity : O(n)

Is there any other way to reduce the space complexity? Please help.

Jayapriya Surendran
  • 1
  • 3
  • You need to clarify more. Time complexity? Space complexity? O(n)? – RaminS Jan 16 '16 at 00:28
  • I've never heard an "array of X" being referred to as a "stream of X". Are you sure you're interpreting your assignment correctly? – Andreas Jan 16 '16 at 00:52
  • This question looks like a duplicate to: http://stackoverflow.com/questions/15752180/how-to-get-unique-items-from-an-array. – DevilsHnd - 退職した Jan 16 '16 at 01:05
  • @DevilsHnd No, the link you provide would turn the example `1,2,3,4,2,3,4` into `1,2,3,4` (duplicates removed), while this assignment is to produce `2,3,4,2,3,4` (remove values occurring once only). – Andreas Jan 16 '16 at 01:08
  • There is a way to solve this problem in Space Complexity O(1), but the time complexity goes to n squared. Is this what you are asking? – Ian Mc Jan 16 '16 at 01:27

2 Answers2

1

For better performance, use Map<Integer, AtomicInteger>, so you can simply update the mapped counter, instead of boxing a new value every time you increment the counter. This will also reduce amount of garbage produced, which could be considered a reduction in memory footprint, even though it technically isn't.

For reduced memory footprint, don't use List<Integer> or Integer[]. Boxing all the values into Integer is a lot of object overhead, and creating a list first, then the final array, means consuming 2 times the number of references.

Instead, once the map has been built, count the number of values to be removed, then create the result array directly and fill it. No boxing and no space wasted on a List.

I'll leave it to you to adjust the code for these improvements.

Andreas
  • 154,647
  • 11
  • 152
  • 247
  • This solution does not improve upon space complexity O(n). However from a Java perspective, there are many excellent concepts introduced here. – Ian Mc Jan 16 '16 at 01:42
  • @IanMc True. It reduces memory footprint, but not complexity. It's still linear to size of input, it's just a flatter curve. – Andreas Jan 16 '16 at 01:49
1

You could use Java8:

Arrays.stream(arr).collect(Collectors.groupingBy(Function.identity()).
       entrySet().stream().filter(e -> e.getValue().size() != 1).
       map(e -> e.getValue()).toArray(int[]::new);