Find the largest unduplicated number in an ArrayList

Question

I need an algorithm that finds the largest number that only appears once in an ArrayList.

For example, suppose I have an ArrayList<Integer> with elements

[3, 3, 3, 6, 7, 8, 8, 9, 9, 9].

Here, the algorithm I need would produce the number 7, because it is the largest unduplicated number in the list.

Preconditions:

• The input list is not guaranteed to be sorted.

• The input list will always contain at least one non-duplicate number.

Answer 1

If we assume the input list is sorted, we should be able to do this in O(N), with no additional space necessary.

public static Integer maxUnduplicatedVal(ArrayList<Integer> lst){
    if(lst == null || lst.isEmpty()) 
        return null;
    if(lst.size() == 1) return lst.get(0);

    if(! lst.get(lst.size() - 1).equals(lst.get(lst.size() - 2))) 
        return lst.get(lst.size() - 1);

    for(int i = lst.size() - 2; i > 0; i--){
        Integer next = lst.get(i + 1);
        Integer here = lst.get(i);
        Integer prev = lst.get(i - 1);
        if(! next.equals(here) && ! prev.equals(here)) return here;
    }

    if(! lst.get(0).equals(lst.get(1))) return lst.get(0);
    return null; //All duplicates
}

If it is not always sorted, the fastest way is to create a copy of the list then remove duplicates and just call the max function in Collections. Making the copy is a really good idea - getters really shouldn't alter the collection they receive. (This includes sorting the given set).

private static List<Integer> getUniques(List<Integer> list) {
    HashMap<Integer, Boolean> flagMap = new HashMap<>();

    //Total Loop: O(N)
    for(Integer i : list){
        if(flagMap.containsKey(i)) flagMap.put(i, false); //O(1)
        else flagMap.put(i, true); //O(1)
    }

    ArrayList<Integer> result = new ArrayList<Integer>();

    //Total Loop: O(N)
    for(Integer i : list){
        if(flagMap.get(i)) result.add(i); //O(1)
    }
    return result;
}

public static Integer maxUnduplicatedVal(ArrayList<Integer> lst){
    List<Integer> lstCopy = getUniques(lst);
    return Collections.max(lstCopy);
}

This is still O(N), albiet with some extra space requirements.

Answer 2

Collections.frequency might be of use here...

    Integer[] myArr = {3, 3, 3, 6, 7, 8, 8, 9, 9, 9}; // sample array
    ArrayList<Integer> myList = new ArrayList<Integer>(Arrays.asList( myArr ) );

    // creating a set from an ArrayList will remove any duplicate elements
    HashSet<Integer> mySet = new HashSet<Integer>(myList);

    /* Make sure list isn't empty or null here, etc. */

    Integer largest = null;

    // iterate through the set, ensuring you don't examine duplicates
    for ( Integer i : mySet ) {

        // if the frequency of that element is 1, we can compare it
        if ( Collections.frequency(myList, i) == 1 )
        {
            if ( largest == null )
            {
                largest = i; // base case
            } else if ( i > largest ) {
                largest = i;
            }
        }
    }

    System.out.println( "The largest non-duplicate is " + largest );
    // or return, etc.

Answer 3

The Best way is to find the unduplicated element in the sorted array of list of elements. Hence by doing this we can segregate the list of unduplicated elements and then we can find the largest in the list obtained.

Would recommend to refer to link below for more details.

Find the unduplicated element in a sorted array

-Bruce

Answer 4

Here is the Algo

1) First do Collections.sort(list) if list is not already sorted

2)Start from the last as it is the largest number and get its index

3)Check if number at that that index is equal to number at index-1, if yes it is the largest duplicate number other wise repeat this step for index-1