Third Maximum Number

Problem

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int thirdMax(vector<int>& nums) {
      int m1 = INT_MIN, m2 = INT_MIN, m3 = INT_MIN;
      for (int e : nums) {
        if (e > m1) {
          int tmp = m1;
          m1 = e;
          int tmp2 = m2;
          m2 = tmp;
          m3 = tmp2;
        } else if (e > m2) {
          int tmp = m2;
          m2 = e;
          m3 = tmp;
        } else if (e > m3) {
          m3 = e;
        }
      }

      // we should only return m3 if m3 was updated
      if (m3 > INT_MIN) {
        return m3;
      } else if (m2 > INT_MIN) {
        return m2;
      }

      return m1;
    }
};

Oops! Read the question carefully.

If it does not exist, return the maximum number.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int thirdMax(vector<int>& nums) {
      int m1 = INT_MIN, m2 = INT_MIN, m3 = INT_MIN;
      for (int e : nums) {
        if (e > m1) {
          int tmp = m1;
          m1 = e;
          int tmp2 = m2;
          m2 = tmp;
          m3 = tmp2;
        } else if ((e > m2) && (e != m1)) {
          int tmp = m2;
          m2 = e;
          m3 = tmp;
        } else if ((e > m3) && (e != m2)) {
          m3 = e;
        }
      }

      // we should only return m3 if m3 was updated
      if (m3 > INT_MIN) {
        return m3;
      }
      return m1;
    }
};

There still a problem with this!

For [3,2,3]we see m1 = 3, m2 = 3,m3 = 2! 😱

We should have seen m1 = 3, m2 = 2,m3 = INT_MIN!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int thirdMax(vector<int>& nums) {
      int m1 = INT_MIN, m2 = INT_MIN, m3 = INT_MIN;
      for (int e : nums) {
        if (e > m1) {
          int tmp = m1;
          m1 = e;
          int tmp2 = m2;
          m2 = tmp;
          m3 = tmp2;
        } else if ((e > m2) && (e != m1)) {
          int tmp = m2;
          m2 = e;
          m3 = tmp;
        } else if ((e > m3) && (e != m2)) {
          m3 = e;
        }
      }

      //printf("%d %d %d\n", m1,m2,m3);
      // we should only return m3 if m3 was updated
      if (m3 > INT_MIN) {
        return m3;
      }
      return m1;
    }
};

Well this fails the testcase below.

1
2
3
Input: [1,2,2,5,3,5]
Output: 5
Expected: 2

The reason is because we need to ensure we check both m1 and m2!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int thirdMax(vector<int>& nums) {
      int m1 = INT_MIN, m2 = INT_MIN, m3 = INT_MIN;
      for (int e : nums) {
        if (e > m1) {
          int tmp = m1;
          m1 = e;
          int tmp2 = m2;
          m2 = tmp;
          m3 = tmp2;
        } else if ((e > m2) && (e != m1)) {
          int tmp = m2;
          m2 = e;
          m3 = tmp;
        } else if ((e > m3) && (e != m2) && (e != m1)) {
          m3 = e;
        }
      }

      // we should only return m3 if m3 was updated
      if (m3 > INT_MIN) {
        return m3;
      }
      return m1;
    }
};

Oh great. Now it fails here… 🤕
Ah you got me there!

1
2
3
4

Input: [1,2,-2147483648]
Output: 2
Expected: -2147483648

Well we have no way of knowing right now that the m3 was set to INT_MIN or was never updated.
If we has used a data structure like a set this might have been simpler and cleaner.

Well we can possibly use a flag to denote when all variables have been touched and when they have not. Then we also need to test >= as opposed to >.

Attempt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int thirdMax(vector<int>& nums) {
      int m1 = INT_MIN, m2 = INT_MIN, m3 = INT_MIN;
      bool m3updated = false;
      for (int e : nums) {
        if (e >= m1) {
          int tmp = m1;
          m1 = e;
          int tmp2 = m2;
          m2 = tmp;
          m3 = tmp2;
        } else if ((e >= m2) && (e != m1)) {
          int tmp = m2;
          m2 = e;
          m3 = tmp;
        } else if ((e >= m3) && (e != m2) && (e != m1)) {
          m3 = e;
          m3updated = true;
        }
      }

      // we should only return m3 if m3 was updated
      if (m3 > INT_MIN) {
        return m3;
      }
      return m1;
    }
};

This is not a good approach.

Let’s go back and think about the requirement a bit more. Well the numbers are ints. So we cannot initialize to INT_MIN. 🤔

OK so what can we initialize this to?

How about LONG_MIN 💡!

Accepted

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int thirdMax(vector<int>& nums) {
      long m1 = LONG_MIN, m2 = LONG_MIN, m3 = LONG_MIN;

      for (int e : nums) {
        if ((long)e > m1) {
          long tmp = m1;
          m1 = (long) e;
          long tmp2 = m2;
          m2 = tmp;
          m3 = tmp2;

        } else if (((long)e > m2) && ((long)e != m1)) {
          long tmp = m2;
          m2 = (long)e;
          m3 = tmp;

        } else if (((long)e > m3) && ((long)e != m2) && ((long)e != m1)) {
          m3 = e;

        }
      }

      // we should only return m3 if m3 was updated
      if (m3 > LONG_MIN) {
        return m3;
      }
      return m1;
    }
};

Nice 👍

But this has an obvious shortfall. What if the inputs are long? Well we can use long long?

But you see the limitations.

A set would be cleaner.