1
\$\begingroup\$

I wrote code to filter for duplicate elements in an array. I'd like to know your opinion, whether it's efficient at all, or if there's too many objects created, use of both array and list. That's in preparation for an interview. I'm not interested in lambdas (distinct) or helper methods, I'd like to see where I can improve and understand what's efficient or not in what I wrote, also without using Set, HashSet.

public class Duplicate {
    public static void main (String [] args){
        // filter duplicate elements
        int [] arr = {5,4,3,5,4,6,7,8,6};
        Arrays.sort(arr);
        int length = arr.length;
        List<Integer> list = new ArrayList<>();
        list.add(arr[0]);
        for(int i =0; i <length-1;i++){
            if(arr[i] != arr[i+1]){
                list.add(arr[i+1]);
            }
        }
        System.out.println(Arrays.toString(list.toArray()));
    }
}
\$\endgroup\$
2
  • \$\begingroup\$ You can add the items to a Set instead of a List to avoid duplicates. \$\endgroup\$
    – Oboe
    Jul 28 '20 at 23:49
  • \$\begingroup\$ Sorry I forgot to mention, without using a set. \$\endgroup\$
    – Patrick
    Jul 29 '20 at 8:59
0
\$\begingroup\$

You can add the items to a Set instead of a List to avoid duplicates. That way you delegate to Set for uniqueness:

int [] arr = {5, 4, 3, 5, 4, 6, 7, 8, 6};

Set<Integer> set = new HashSet<>();

int length = arr.length;

for(int i = 0; i < length; i++){
    set.add(arr[i]);
}

System.out.println(Arrays.toString(set.toArray()));
\$\endgroup\$
4
  • \$\begingroup\$ Have you tested this on an array with only one element? \$\endgroup\$
    – dnault
    Jul 29 '20 at 1:22
  • \$\begingroup\$ I copy the loop from the question. Now is fixed. \$\endgroup\$
    – Oboe
    Jul 29 '20 at 3:29
  • \$\begingroup\$ Sorry I forgot to mention, without using a Set. \$\endgroup\$
    – Patrick
    Jul 29 '20 at 8:58
  • \$\begingroup\$ dnault - Yes, let's take into consideration there's an if statement to filter for that, this is to focus more on the working logic \$\endgroup\$
    – Patrick
    Jul 29 '20 at 9:02
0
\$\begingroup\$

It may be important to the interviewer that you can find a solution without sorting (I don't know the full context of the interview question), for example if the original order is important or if the elements can not be compared in a sortable way. A solution that would take O(n^2) time but preserve order, and take O(1) space is to go element by element, search the rest of the data structure for a repetition of the current element and removing it. It would take O(n^2) if you used a structure with O(1) removals, such as a linked list.

\$\endgroup\$
2
  • \$\begingroup\$ No, I don't get a null pointer exception, as it stops one before the length of the array, i + 1 still works. \$\endgroup\$
    – Patrick
    Jul 29 '20 at 9:01
  • \$\begingroup\$ @Patrick Oh right, sorry, that was lazy on my part. I’ll edit it so it doesn’t confuse anyone \$\endgroup\$
    – Diego Esparza
    Jul 29 '20 at 14:32
0
\$\begingroup\$

This problem is very simple in only a few lines of code, as long as we know what the constraints on the input are:

int [] arr = {5,4,3,5,4,6,7,8,6};
int maxPossibleInputValue = 9;
...
List<Integer> list = new ArrayList<>();
byte[] tracker = new byte[maxPossibleInputValue + 1];
for (int i = 0; i < arr.length; i++)
{
    if (tracker[arr[i]]++ == 0)
    {
        list.add(arr[i]);
    }
}

Only works when we know the range of input possible due to memory consumption, but it will be fast - O(n) with only a single heap allocation.

If the value range will exceed memory constraints (i.e. the entire 32 bit int range instead of "all digits under 1000" or such), then we may have to implement our own simple hashset...

i.e.

List<Integer> mainRoutine(int[] arr)
{
    List<Integer> list = new ArrayList<>();
    MyNode[] tracker = new MyNode[65536];
    for (int i = 0; i < arr.length; i++)
    {
        int segment = arr[i] % tracker.length;
        if (tracker[segment] == null) || !tracker[segment].has(arr[i]))
        {
            list.add(arr[i]);
        }
        MyNode newNode = new MyNode(arr[i], tracker[segment]);
        tracker[segment] = newNode;
    }
    return list;
}

...
...

private static class MyNode
{
    private final int val;
    private MyNode child;

    private MyNode(int val, MyNode child)
    {
        this.val = val;
        this.child = child;
    }

    boolean has(int val)
    {
        return (this.val == val) || (child != null && child.has(val);
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy