How do a find the maximum non-repeating number in an integer array?

Question

Suppose I have an unsorted integer array {3, -1, 4, 5, -3, 2, 5}, and I want to find the maximum non-repeating number (4 in this case) (5 being invalid as it is repeated). How can I achieve this?

• user180940: Sort the array (O(n log n)) and then iterate from the end of the array, taking the middle element when I see three different elements (O(n)).
• Always Learning: That should work as long as there are at least 3 entries in the list. Did you try it and it didn't work properly?
• user180940: I'm pretty sure it works, at the expense of clarity (have to handle the 0,1,2 array sizes externally) but more importantly can it be done in less than O(n log n).

Answer 1

Use an unordered map to count the frequencies of each element. (As an optimization, keep track of largest element encountered and skip elements lower than that.) Then, scan the map to find out the largest element with frequency exactly equal to 1.

template <typename T> // numeric T
pair<T, bool> FindMaxNonRepeating(vector<T> const& vec) {
 unordered_map<T, int> elem2freq;
 for (auto const& elem : vec) {
 elem2freq[elem] += 1;
 }
 T largest_non_repetitive = std::numeric_limits<T>::min();
 bool found = false;
 for (auto const& item : elem2freq) {
 if (item.first > largest_non_repetitive && item.second == 1) {
 largest_non_repetitive = item.first;
 found = true;
 }
 }
 return {largest_non_repetitive, found};
}

This runs in time complexity O(n) and requires space complexity O(n).

• gsamaras: Ah damn you Arun, I thought something like that while having lunch! Of course, this would need more space, as you mentioned, +1.

Answer 2

1. Sort the array in descending order.
2. Begin from top element and store it a variable, say max.
3. Check next element with max, if they are the same, repeat until you find the next max, otherwise, you found the max non-repeated number.

Time complexity: O(nlogn)

c++ implementation, based on my Sort (C++):

#include <algorithm>
#include <iostream>
#include <vector>
#include <limits>
#include <cstddef>
using namespace std;
void printVector(vector<int>& v)
{
 for(vector<int>::iterator it = v.begin() ; it != v.end() ; it++)
 cout << *it << ' ';
 cout << endl;
}
bool compar(const int& a, const int& b)
{
 return (a > b) ? true : false;
}
int main()
{
 vector<int> v = {3, -1, 4, 5, -3, 2, 5};
 cout << "Before sorting : " << endl;
 printVector(v);
 sort(v.begin(), v.end(), compar);
 cout << endl << "After sorting : " << endl;
 printVector(v);
 int max_non_repeat = numeric_limits<int>::min();
 for(unsigned int i = 0; i < v.size(); ++i)
 {
 if(max_non_repeat == v[i])
 max_non_repeat = numeric_limits<int>::min();
 else if(v[i] > max_non_repeat)
 max_non_repeat = v[i];
 }
 cout << "Max non-repeated element: " << max_non_repeat << endl;
 return 0;
}

Output:

C02QT2UBFVH6-lm:~ gsamaras$ g++ -Wall -std=c++0x main.cpp 
C02QT2UBFVH6-lm:~ gsamaras$ ./a.out 
Before sorting : 
3 -1 4 5 -3 2 5 
After sorting : 
5 5 4 3 2 -1 -3 
Max non-repeated element: 4

---

For maximum pleasure, do base your (a different) approach on How to find max. and min. in array using minimum comparisons? and modify it accordingly.

• stackoverflowuser2010: Sorting the array takes time O(n log n) in place or O(n) not in place.