# Short easy C++ using set

• Track the largest three values in a set.

``````int thirdMax(vector<int>& nums) {
set<int> top3;
for (int num : nums) {
top3.insert(num);
if (top3.size() > 3)
top3.erase(top3.begin());
}
}
``````

Alternatively (not sure which one I like better):

``````int thirdMax(vector<int>& nums) {
set<int> top3;
for (int num : nums)
if (top3.insert(num).second && top3.size() > 3)
top3.erase(top3.begin());
}``````

• std::set usually uses a red-black tree, so wouldn't this be nlogn?

• @sean46 Depends on what you mean with "nlogn".

• Since we only have 3 elements, insert/delete is constant time operations. Don't stick to O(nlog n) concept. We only care about big O when the things we are dealing with is big.

• I got the same idea using python:

``````class Solution(object):
def thirdMax(self, nums):
l = []
for n in set(nums):
bisect.insort(l, -n)
if len(l)>3:
l.pop()
return -l[2] if len(l)>2 else -l[0]
``````

• @o_sharp Could also use

``````        bisect.insort(l, -n)
del l[3:]
``````

or

``        l = sorted(l + [-n])[:3]``

• My HashSet approach in Java, though not good in performance(25ms):

``````public int thirdMax(int[] nums) {
Set<Integer> s = new HashSet<Integer>();
int max = nums[0];
int left = max;
for(int num : nums){
//push into set
//update max
if(max < num) max = num;
//keep track min in set
if(s.size() <= 3){
left = Math.min(num, left);
}
else{
s.remove(Math.min(left, num));
left = Math.max(left,num);
for(int setNum : s){
left =Math.min(setNum, left);
}
}
}

return s.size()<3 ? max:left;
}
``````

Please tell me if there is any improvement in my code

• Same solution in Java, runs in 20ms.

``````public class Solution {
public int thirdMax(int[] nums) {
TreeSet<Integer> set = new TreeSet<>();
for(int num : nums) {
if(set.size() > 3) {
set.remove(set.first());
}
}
return set.size() < 3 ? set.last() : set.first();
}
}
``````

• This post is deleted!

• Track the largest three values in a set.

``````int thirdMax(vector<int>& nums) {
set<int> top3;
for (int num : nums) {
top3.insert(num);
if (top3.size() > 3)
top3.erase(top3.begin());
}
}
``````

Alternatively (not sure which one I like better):

``````int thirdMax(vector<int>& nums) {
set<int> top3;
for (int num : nums)
if (top3.insert(num).second && top3.size() > 3)
top3.erase(top3.begin());
}``````

• I used the same solution and it costs 9ms.
Then I reduced the time to 6ms by avoiding some sorting...

``````    int thirdMax(vector<int>& nums) {
set<int> top3;
for (int num : nums)
{
if (top3.size() < 3 || num > *top3.begin())
top3.insert(num);
if (top3.size() > 3)
top3.erase(top3.begin());
}
return (top3.size() < 3) ? *top3.rbegin() : *top3.begin();
}
``````

• @StefanPochmann

I don't think using a set in the way that you are in your solution is consistent with the spirit of this question. Here's my 3n, 10 ms approach in Java:

``````public int thirdMax(int[] nums) {
Integer[] maxs = new Integer[3];
for (int num : nums) {
int candidate = num;
for (int i = maxs.length - 1; i >= 0; i --) {
if (maxs[i] == null) {
maxs[i] = candidate;
break;
} else if (candidate > maxs[i]) {
int tmp = maxs[i];
maxs[i] = candidate;
candidate = tmp;
} else if (candidate == maxs[i]) {
// avoid duplicates
break;
}
}
}
return maxs[0] != null ? maxs[0] : maxs[2];
}
``````

• I don't think using a set in the way that you are in your solution is consistent with the spirit of this question.

Why not?

• @StefanPochmann I signed back on just now to retract my statement. I was confused when I wrote my original comment last night. Your solution is good. If I'm correct, it runs in n * log(3) time, which is linear.

• one thing I want to make sure : is the set in c++ in order?

• @bin01 Similar solution in Java, runs in 17ms.

``````public int thirdMax(int[] nums) {
TreeSet<Integer> ts = new TreeSet<>();
for(int num:nums){