LeetCode - Algorithms - 414. Third Maximum Number

Problem

414. Third Maximum Number

Java

my solution

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(int[] nums) {
        final int N = nums.length;
        int max = nums[0];
        for (int i = 1; i < N; i++) {
            if (nums[i] > max)
                max = nums[i];
        }
        int m2 = Integer.MIN_VALUE;
        for (int i = 0; i < N; i++) {
            if (nums[i] < max && nums[i] > m2)
                m2 = nums[i];
        }
        long m3 = Long.MIN_VALUE;
        for (int i = 0; i < N; i++) {
            if (nums[i] < m2 && nums[i] > m3)
                m3 = nums[i];
        }
        return m3 > Long.MIN_VALUE ? new Long(m3).intValue() : max;
    }
}

Submission Detail

  • 26 / 26 test cases passed.
  • Runtime: 1 ms, faster than 90.82% of Java online submissions for Third Maximum Number.
  • Memory Usage: 39.2 MB, less than 7.88% of Java online submissions for Third Maximum Number.

PriorityQueue and HashSet

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.*;

class Solution {
    public int thirdMax(int[] nums) {
        Queue<Integer> q = new PriorityQueue<Integer>();
        Set<Integer> set = new HashSet<Integer>();
        for (int i : nums) {
            if (!set.contains(i)) {
                set.add(i);
                q.add(i);
            }
            if (q.size() > 3) {
                set.remove(q.poll());
            }
        }
        if (q.size() < 3) {
            while (q.size() > 1)
                q.poll();
        }
        return q.peek();
    }
}

Submission Detail

  • 26 / 26 test cases passed.
  • Runtime: 5 ms, faster than 21.06% of Java online submissions for Third Maximum Number.
  • Memory Usage: 38.7 MB, less than 10.02% of Java online submissions for Third Maximum Number.

TreeSet

1
2
3
4
5
6
7
8
9
10
11
12
13
import java.util.*;

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

Submission Detail

  • 26 / 26 test cases passed.
  • Runtime: 4 ms, faster than 39.33% of Java online submissions for Third Maximum Number.
  • Memory Usage: 38.6 MB, less than 10.02% of Java online submissions for Third Maximum Number.

javascript

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
/**
 * @param {number[]} nums
 * @return {number}
 */
var thirdMax = function(nums) {
    var max=nums[0],min=nums[0];
    for(var i=1;i<nums.length;i++) {
        if (nums[i]>max)
            max = nums[i];
        if (nums[i]<min)
            min = nums[i];
    }
    var lowguard = min-1;
    var m2 = lowguard;
    for(var i=0;i<nums.length;i++) {
        if (nums[i]<max && nums[i]>m2)
            m2 = nums[i];
    }
    var m3 = lowguard;
    for(var i=0;i<nums.length;i++) {
        if (nums[i]<m2 && nums[i]>m3)
            m3 = nums[i];
    }
    return m3!=lowguard?m3:max;
};

Submission Detail

  • 26 / 26 test cases passed.
  • Runtime: 80 ms, faster than 72.32% of JavaScript online submissions for Third Maximum Number.
  • Memory Usage: 38.9 MB, less than 5.00% of JavaScript online submissions for Third Maximum Number.