C++ Coding Exercise – Find Third Maximum in O(n)


learn-to-code C++ Coding Exercise - Find Third Maximum in O(n) algorithms c / c++ data structure learn to code

learn-to-code

Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).
Example 1:
Input: [3, 2, 1]
Output: 1
Explanation: The third maximum is 1.
Example 2:
Input: [1, 2]
Output: 2
Explanation: The third maximum does not exist, so the maximum (2) is returned instead.
Example 3:
Input: [2, 2, 3, 1]
Output: 1
Explanation: Note that the third maximum here means the third maximum distinct number.
Both numbers with value 2 are both considered as second maximum.

The third maximum number should ignore duplicate numbers, for example, [1, 2, 2, 3] the third maximum is 1 instead of 2.

Using std::set

The std::set keeps a sorted unique set of elements. We can update the set when iterating the numbers, keeping a maximum 3 numbers. If there are more than 3 elements in the set, we erase the smallest one. As we can’t directly access the elements in the set by index, we use the iterator rbegin and begin to retrieve the biggest and smallest number respectively.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int thirdMax(vector<int>& nums) {
        set<int> data;
        for (const auto &n: nums) {
            data.insert(n);
            if (data.size() > 3) {
                data.erase(data.begin()); // removing the smallest
            } 
        }
        return data.size() < 3 ? *data.rbegin() : *data.begin();
    }
};
class Solution {
public:
    int thirdMax(vector<int>& nums) {
        set<int> data;
        for (const auto &n: nums) {
            data.insert(n);
            if (data.size() > 3) {
                data.erase(data.begin()); // removing the smallest
            } 
        }
        return data.size() < 3 ? *data.rbegin() : *data.begin();
    }
};

Using std::priority_queue

By default, std::priority_queue keeps a queue that guarantees top() returns current maximum in the queue. We can revert the priority by using std::greater in the third parameter. It is based on the heap where the construction of heap is O(nlogn). However, as we keep the maximum size of 3, the actual complexity of building the priority queue when iterating the number is O(logn). We use std::unordered_set to make sure no duplicates are inserted into the priority queue. Likewise, we maintain the queue of maximum size 3 when iterating the numbers.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int thirdMax(vector<int>& nums) {
        unordered_set<int> cache;
        priority_queue<int, vector<int>, std::greater<int>> data; // priority in non-descending order
        for (const auto &n: nums) {
            if (cache.count(n)) {
                continue;  // skip the duplicates
            }
            cache.insert(n); // mark it 
            data.push(n); // insert into the priority queu
            if (data.size() > 3) {
                data.pop();
            } 
        }
        if (data.size() < 3) {
            while (data.size() > 1) {
                data.pop();  // removing numbers from small to big
            }
            return data.top(); // the maximum of less 3
        }
        return data.top(); // third maximum
    }
};
class Solution {
public:
    int thirdMax(vector<int>& nums) {
        unordered_set<int> cache;
        priority_queue<int, vector<int>, std::greater<int>> data; // priority in non-descending order
        for (const auto &n: nums) {
            if (cache.count(n)) {
                continue;  // skip the duplicates
            }
            cache.insert(n); // mark it 
            data.push(n); // insert into the priority queu
            if (data.size() > 3) {
                data.pop();
            } 
        }
        if (data.size() < 3) {
            while (data.size() > 1) {
                data.pop();  // removing numbers from small to big
            }
            return data.top(); // the maximum of less 3
        }
        return data.top(); // third maximum
    }
};

using std::vector

Using vector is quite similar to set, however, you will need to skip the duplicate numbers. We have a find() and sort() in the for loop, however the complexity is still O(n) as these two method’s running time complexity is independent of the problem size.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int thirdMax(vector<int>& nums) {
        vector<int> max3;
        for (const auto &n: nums) {
            if (std::find(max3.begin(), max3.end(), n) != max3.end()) {
                continue; // skip the duplicates
            }
            max3.push_back(n);
            sort(max3.begin(), max3.end()); // sort array of size 3
            if (max3.size() > 3) {
                max3.erase(max3.begin()); // remove the smallest one
            }
        }
        if (max3.size() == 3) {
            return max3[0];
        } else {
            return max3[max3.size() - 1];
        }
    }
};
class Solution {
public:
    int thirdMax(vector<int>& nums) {
        vector<int> max3;
        for (const auto &n: nums) {
            if (std::find(max3.begin(), max3.end(), n) != max3.end()) {
                continue; // skip the duplicates
            }
            max3.push_back(n);
            sort(max3.begin(), max3.end()); // sort array of size 3
            if (max3.size() > 3) {
                max3.erase(max3.begin()); // remove the smallest one
            }
        }
        if (max3.size() == 3) {
            return max3[0];
        } else {
            return max3[max3.size() - 1];
        }
    }
};

You may also like: C++ 编程练习题 – 找出第三大的数

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
660 words
Last Post: Coding Exercise - Find Max Consecutive Ones
Next Post: Algorithms to Find Maximum Depth of N-ary Tree (C++)

The Permanent URL is: C++ Coding Exercise – Find Third Maximum in O(n)

Leave a Reply