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\$
  • \$\begingroup\$ You can add the items to a Set instead of a List to avoid duplicates. \$\endgroup\$ – Oboe Jul 28 at 23:49
  • \$\begingroup\$ Sorry I forgot to mention, without using a set. \$\endgroup\$ – Patrick Jul 29 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()));
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Have you tested this on an array with only one element? \$\endgroup\$ – dnault Jul 29 at 1:22
  • \$\begingroup\$ I copy the loop from the question. Now is fixed. \$\endgroup\$ – Oboe Jul 29 at 3:29
  • \$\begingroup\$ Sorry I forgot to mention, without using a Set. \$\endgroup\$ – Patrick Jul 29 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 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.

| improve this answer | |
\$\endgroup\$
  • \$\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 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 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);
    }
}
| improve this answer | |
\$\endgroup\$

Your Answer

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