Given an array of integers A, return the largest integer that only occurs once. If no integer occurs once, return -1.

Example 1:
Input: [5,7,3,9,4,9,8,3,1]
Output: 8
Explanation:
The maximum integer in the array is 9 but it is repeated. The number 8 occurs only once, so it’s the answer.

Example 2:
Input: [9,9,8,8]
Output: -1

Explanation:
There is no number that occurs only once.

Note:
1 <= A.length <= 2000
0 <= A[i] <= 1000

Largest Unique Number: Sort and Check

You can sort the numbers and that will cost you O(nlogn) complexity. Once the array is sorted, you can skip the duplicate numbers easily by checking the value at the next index and the previous index. To avoid boundary checks, two values (INT_MIN and INT_MAX) are pushed to the front and the rear of the array respectively.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    int largestUniqueNumber(vector<int>& A) {
        // push dummy values at front and end
        // to avoid boundary checks
        A.push_back(INT_MAX);
        A.push_back(INT_MIN);
        sort(begin(A), end(A));
        for (int i = A.size() - 2; i > 0; -- i) {
            if (A[i] == A[i - 1]) continue;
            if (A[i] == A[i + 1]) continue;
            return A[i];
        }
        return -1;
    }
};

class Solution {
public:
    int largestUniqueNumber(vector<int>& A) {
        // push dummy values at front and end
        // to avoid boundary checks
        A.push_back(INT_MAX);
        A.push_back(INT_MIN);
        sort(begin(A), end(A));
        for (int i = A.size() - 2; i > 0; -- i) {
            if (A[i] == A[i - 1]) continue;
            if (A[i] == A[i + 1]) continue;
            return A[i];
        }
        return -1;
    }
};

This algorithm uses constant space O(1).

Bucket Counting: Return the Largest Unique Number in O(N)

As the inputs are tightly constrainted to integers from 0 to 1000, we can have a O(1) 1001 buckets and do the counting in O(N) time. Once finished, we can start from 1000 and check downwards in O(1) time, return the largest unique number if it only appears once.

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    int largestUniqueNumber(vector<int>& A) {
        int c[1001] = { 0 };
        for (const auto &n: A) {
            c[n] ++;
        }
        for (int i = 1000; i >= 0; -- i) {
            if (c[i] == 1) return i;
        }
        return -1;
    }
};

class Solution {
public:
    int largestUniqueNumber(vector<int>& A) {
        int c[1001] = { 0 };
        for (const auto &n: A) {
            c[n] ++;
        }
        for (int i = 1000; i >= 0; -- i) {
            if (c[i] == 1) return i;
        }
        return -1;
    }
};

The algorithm uses constant space and only require O(N) time.

Using Multiset to Count the Numbers

To generalise the solution, we can use a multiset (or a hash map) to do the counting. However, this needs two scans: the first scan will record the numbers in the multi-set or hash map and the second round, each non-qualified number (duplicate) will be skipped. And we can easily obtain a maximum from the rest.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    int largestUniqueNumber(vector<int>& A) {
        unordered_multiset<int> dup;
        int ans = -1;
        for (const auto &n: A) {
            dup.insert(n);
        }
        for (const auto &n: A) {
            if (dup.count(n) == 1) {
                ans = max(ans, n);
            }
        }        
        return ans;
    }
};

class Solution {
public:
    int largestUniqueNumber(vector<int>& A) {
        unordered_multiset<int> dup;
        int ans = -1;
        for (const auto &n: A) {
            dup.insert(n);
        }
        for (const auto &n: A) {
            if (dup.count(n) == 1) {
                ans = max(ans, n);
            }
        }        
        return ans;
    }
};

The time complexity is O(N) and the space complexity is also O(N).

You can use the Functional Programming to solve this problem: How to Find the Largest Unique Number in Array using Javascript (Functional Programming), or in Python: Python Method to Find the Largest Unique Number in an Array

–EOF (The Ultimate Computing & Technology Blog) —