Third Maximum Number

Problem

Given an integer array nums, return the third distinct maximum number in this array. If the third maximum does not exist, return the maximum number.

Follow up: Can you find an O(n) solution?

Constraints

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1

Solution

The problem Third Maximum Number can be solved using an ordered set to keep track of 3 largest numbers that are unique.

Implementation

class Solution
{
  public:
    int thirdMax(vector<int> &nums)
    {
        set<int> ret;
        for (int num : nums)
        {
            ret.insert(num);
            if (ret.size() == 4)
                ret.erase(ret.begin());
        }

        return ret.size() < 3 ? *ret.rbegin() : *ret.begin();
    }
};