Find the highest unique element in an array

Question

Here is my approach. Unique element means that element should present only once in the array.

import java.io.IOException;
import java.util.Comparator;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;
import java.util.Map.Entry;

public class Unique {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        // Used TreeMap to store data in descending order to return maximum unique value
        Map<Integer, Integer> map = new TreeMap<Integer, Integer>(
                new Comparator<Integer>() {
                    public int compare(Integer o1, Integer o2) {
                        return o2.compareTo(o1);
                    }
                });
        // Add into map if input is not present. If already present, increase count
        for (int i = 0; i < n; i++) {
            int input = sc.nextInt();
            if (map.containsKey(input))
                map.put(input, map.get(input) + 1);
            else
                map.put(input, 1);

        }

        // Check for a entry with value 1. If not present print -1 else traverse
        // the map and print first key with value 1.
        if (map.containsValue(1)) {
            for (Entry<Integer, Integer> entry : map.entrySet()) {

                if (entry.getValue() == 1) {
                    System.out.print(entry.getKey() + " ");
                    break;
                }

            }
        } else
            System.out.println(-1);

    }
}

Sample input:

n=5
9 8 8 9 5

Desired Output:

5

Please critique my approach and suggest better way to solve this problem.

Answer 1

Your approach is a little bit complicated: you're building a TreeMap that is sorted in descending order of their keys. The value for each key is the number of times it appears in the input. Then you are iterating the map to find the first key having the value of 1. There are a couple of notes though.

Use built-in methods

You are constructing a TreeMap sorting in reverse order of their keys with

// Used TreeMap to store data in descending order to return maximum unique value
Map<Integer, Integer> map = new TreeMap<Integer, Integer>(
        new Comparator<Integer>() {
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });

You actually do not need to create a custom comparator for that case. You can use the built-in Collections.reverseOrder(). Also, since Java 7, you can omit the type-declaration with the diamond operator. So you could just have:

Map<Integer, Integer> map = new TreeMap<>(Collections.<Integer>reverseOrder());

Use Java 8 constructs

Starting with Java 8, you can replace the following code

if (map.containsKey(input))
    map.put(input, map.get(input) + 1);
else
    map.put(input, 1);

with the built-in merge(key, value, remappingFunction) method. This will put the given key with the given value if there was no mapping for that key, else it will invoke then given remapping function with the old value and the new one. In this case, we can then replace that code with

map.merge(input, 1, Integer::sum);

which will put the mapping with 1 if there was no key or add 1 to the current value if the mapping already exists.

Add curly braces!

This may sound like a nitpick but it is in fact very important. There are part of your code that doesn't add curly braces, or have it partially, like

if (map.containsKey(input))
    map.put(input, map.get(input) + 1);
else
    map.put(input, 1);

with no curly braces, or

if (map.containsValue(1)) {
    // ...
} else
    System.out.println(-1);

with partial curly braces.

Better to make it consistent and use curly braces everywhere.

Simpler approach

In this problem, we're only interested in keeping the highest number that appear only one time. This means that every numbers which appears more than once can be ignored: we know that it won't be the result. As such, there is no need to store a map with the exact count of each number: we only want to know if it is 1 or not.

Consider the following approach:

• We keep a Set with the running encoutered numbers.
• We keep a Set with the running highest unique numbers.
• For each input, those two sets are updated:
  • If the input was already encountered, we remove it from the set of uniques
  • If the input wasn't encoutered, we add it to both the encoutered and the uniques.

An implementation would be the following:

Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Set<Integer> encounteredInts = new HashSet<>(n);
Set<Integer> uniques = new HashSet<>(n);
for (int i = 0; i < n; i++) {
    int input = sc.nextInt();
    if (encounteredInts.contains(input)) {
        uniques.remove(input);
    } else {
        encounteredInts.add(input);
        uniques.add(input);
    }
}

if (uniques.isEmpty()) {
    System.out.println(-1);
} else {
    System.out.println(Collections.max(uniques));
}

There are clear advantages:

• We do not store information that we don't need in a map: this is net-gain in memory usage.
• We use a Set for look-up, insertion and deletion, which is constant-time: this is net-gain in performance.
• From the final set, we only keep the highest according to the natural ordering of the integer. This is the only operation which runs in linear time, but it is done only once, at the end, when the set will have the minimum amount of numbers to consider.

Answer 2

@Tunaki has given a great answer, and it's all good. The logic he recommends is sound, and so on.

For raw performance, though, you will likely find that your results will improve if you keep things as primitives (no Sets, no Maps, etc.). It also simplifies the logic down, and technically, the "complexity" of the algorithm is about the same, so it will scale as easily.

Avoiding Integer and using int instead has a number of advantages, so, let's do this without Integers.

Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
if (n <= 0) {
    return -1;
}

int[] data = new int[n];
for (int i = 0; i < n; i++) {
    data[i] = sc.nextInt();
}
Arrays.sort(data);

// now scan backwards finding a value that has only 1 instance.
// set the value to something we know is not right.
int value = data[n-1] + 1
int count = 0;
for (int i = n - 1; i >= 0; i--) {
    if (data[i] == value) {
         count++;
    } else {
         if (count == 1) {
             // found largest unique value.
             return value;
         }
         count = 1;
         value = data[i];
    }
}
if (count == 1) {
    // found largest unique value.
    return value;
}
return -1;

Note that you will likely need better error handling on the Scanner.

The complexity in here is \$O(n \log n)\$ which is pretty decent. It has little overhead other than the data array.

The error-handling for empty inputs, and non-existing results (where there are no unique values...) makes this answer incomplete.