Java neat and easy understand solution, O(n) time, O(1) space


  • 89
    Y
        public int thirdMax(int[] nums) {
            Integer max1 = null;
            Integer max2 = null;
            Integer max3 = null;
            for (Integer n : nums) {
                if (n.equals(max1) || n.equals(max2) || n.equals(max3)) continue;
                if (max1 == null || n > max1) {
                    max3 = max2;
                    max2 = max1;
                    max1 = n;
                } else if (max2 == null || n > max2) {
                    max3 = max2;
                    max2 = n;
                } else if (max3 == null || n > max3) {
                    max3 = n;
                }
            }
            return max3 == null ? max1 : max3;
        }
    

  • 12

    I like that your solution does not depend on int.Min to initialize search for max values. Smart using Integer type and null as unset case.


  • 3
    Y

    @jdrogin Yes, I think initialize variables with Integer.MIN_VALUE is not a good idea in this case.


  • 0
    M

    This is the best solution ever...
    I really like this clean and clear and intuitive solution. Thanks.


  • 0
    S

    @yuxiaofei2016 This is best solution I have seen so far. Thanks.
    Would you explain why iniitializing variables with Integer.MIN_VALUE is not a good idea?


  • 2
    Y

    @spencerL Because once you initializing them with Integer.MIN_VALUE, you have to add more logic to figure out the value from the initialization or from the array.


  • 0
    J
    This post is deleted!

  • 3

    @jakeybear41 the solution uses Integer instead of int because it is a nullable type. This way you can use null as a check for "not set", alternately you could use additional bools for this but Integer is a nice way to keep it all together.


  • 0
    J

    @jdrogin could I use n==max1 instead of n.equals(max1)


  • 3

    @jakeybear41 If you use == to compare Integer you will be comparing references not values. you could use a.intValue() == b.intValue() to compare values.


  • 0
    J

    @jdrogin thx so much!!!


  • 9
    R

    If i were the interviewer I would ask "what is not ideal about this solution?"
    And the answer I expect would be that it's not easily modifiable, for example if you want to find 7th maximum instead of 3rd.
    I like the answers using dynamic data structures more because of that reason. (I used a linked list)


  • 0
    Y

    @rmn Yes, you are right.


  • 0
    J

    a nice shot ,instead of Long.MIN_VALUE


  • 0
    F

    A similar but alternative way:

    public class Solution {
        public int thirdMax(int[] nums) {
            Integer[] largest = new Integer[3];
            for (int n: nums) {
                if (largest[0] == null || n > largest[0]) {
                    largest[2] = largest[1];
                    largest[1] = largest[0];
                    largest[0] = n;
                } else if (largest[0] != null && largest[0] > n && (largest[1] == null || n > largest[1])) {
                    largest[2] = largest[1];
                    largest[1] = n;
                } else if (largest[1] != null && largest[1] > n && (largest[2] == null || n > largest[2])) {
                    largest[2] = n;
                }
            }
            return largest[2] == null? largest[0]: largest[2];
        }
    }
    

  • 0
    E

    "elseif" is magic!
    I consider it using separated if logic and code just went very messy!

    public class Solution {
        public int thirdMax(int[] nums) {
            Integer max = null, secondMax = null, thirdMax = null;
            for(int num : nums) {
                if((max != null && max == num) ||
                   (secondMax != null && secondMax == num) ||
                   (thirdMax != null && thirdMax == null)) {
                    continue;
                }
                if(max == null || max < num) {
                    thirdMax = secondMax;
                    secondMax = max;
                    max = num;
                    continue;
                }
                if((secondMax == null && num < max) ||
                   (secondMax != null && num < max && num > secondMax)) {
                    thirdMax = secondMax;
                    secondMax = num;
                    continue;
                }
                if((thirdMax == null && num < secondMax) ||
                   (thirdMax != null && num < secondMax && num > thirdMax)) {
                    thirdMax = num;
                    continue;
                }
            }
            if(thirdMax != null)    return thirdMax;
            else    return max;
        }
    }
    

  • 0
    B
    This post is deleted!

  • 0
    B
    This post is deleted!

  • 0
    B
    This post is deleted!

  • 0
    W

    I have the same idea with you. I wrote it in C++

    class Solution {
    public:
        int thirdMax(vector<int>& nums) {
            long long mx, sec, thr;
            mx = sec = thr = LONG_MIN;
            for (int i = 0; i < nums.size(); i++) {
                if (nums[i] == mx || nums[i] == sec || nums[i] <= thr) {
                    continue;
                }
                if (nums[i] > mx) {
                    thr = sec;
                    sec = mx;
                    mx = nums[i];
                } else if (nums[i] > sec) {
                    thr = sec;
                    sec = nums[i];
                } else if (nums[i] > thr) {
                    thr = nums[i];
                }
            }
            return thr == LONG_MIN ? mx : thr;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.