Array 101 Third Maximum Number in go

Accepted Solutions Runtime Distribution

Accepted Solutions Memory Distribution

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.

Example 1:

Input: nums = [3,2,1]
Output: 1
Explanation:
The first distinct maximum is 3.
The second distinct maximum is 2.
The third distinct maximum is 1.

Example 2:

Input: nums = [1,2]
Output: 2
Explanation:
The first distinct maximum is 2.
The second distinct maximum is 1.
The third distinct maximum does not exist, so the maximum (2) is returned instead.

Example 3:

Input: nums = [2,2,3,1]
Output: 1
Explanation:
The first distinct maximum is 3.
The second distinct maximum is 2 (both 2's are counted together since they have the same value).
The third distinct maximum is 1.

Constraints:

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

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

My code

func thirdMax(nums []int) int {
    first, second, third := -2147483649, -2147483649, -2147483649

    for _, v := range nums {
        if v > third && v != second && v != first {
            third = v
        }
        if third > second {
            second, third = third, second
        }
        if second > first {
            first, second = second, first
        }
    }

    if third != -2147483649 {
        return third
    }
    return first
}

• First, I made with quick sort but It took a lot of time compared to others.
• In Leetcode problem, it was written that O(n) solution will be.
• I used three variable to save
• first if will check whether it is bigger than third. also it must be different with first and second.
• If so, it will go up and swapping.
• Minimum value is -2^31
• Final if condition will return when third is not minimum value-1 or not it will return biggest number.

sample 0 ms submission & sample 2800 KB submission

func thirdMax(nums []int) int {
    min := -1<<63
    a, b, c := min, min, min
    for _, num := range nums {
        if a < num {
            c = b
            b = a
            a = num
        }
        if b < num && num < a {
            c = b
            b = num
        }
        if c < num && num < b{
            c = num
        }
    }
    if c != min {
        return c
    }
    return a
}

• This code used bitwise operation. \ num << 1 (move to left based on bit. ex 2(0010), 2 << 1, 4(0100))
• But i don't know why coder put <<63.
• This code is the opposite of my code.
• A is biggest and C is smallest.
• if condition will check num is biggest or not.
• If biggest, move from a to b, b to c and num to a.
• When num is Bigger than b and smaller than a, move from b to c and num to b.
• Last if condition will check num is bigger than c and less then b.

sample 2 ms submission

func thirdMax(nums []int) int {
    var first,second,third int
    first = nums[0]
    second = -2147483649
    third = -2147483649

    for _,val := range nums[1:] {
        if val > first {
            third = second
            second = first
            first = val
        } else if val > second && val != first {
            third = second
            second = val
        } else if val > third && val != second && val != first {
            third = val
        }
    }

    fmt.Println(first,second,third)

    if len(nums) < 3 {
        return first
    }

    if third == -2147483649 {
        return first
    }

    return third
}

• This code allocate first array value to first.
• rest will be -2^31
• also this for loop skip arr[0] because it was already used to first variable.
• difference is that if condition about second and third will check is same or not.
• but this code has useless if condition.

sample 3 ms submission

func thirdMax(nums []int) int {
    sort.Ints(nums)
    max := make([]int, 0)

    i, last := len(nums)-1, 0
    for i >= 0 {
        if len(max) == 3 {
            break
        }
        if nums[i] != last {
            last = nums[i]
            max = append(max, last)
        }
        i--
    }

    if len(max) < 3 {
        return max[0]
    }
    return max[len(max)-1]
}

• This code used sort.. so I don't recommend this code.
• i will have biggest number (end of array) and last will be 0.
• if len is 3 then it will return max[len(max)-1]
• I don't know why last is 0.
• I reported to Leetcode.

sample 4 ms submission

func thirdMax(nums []int) int {
    max1, max2, max3 := math.MinInt, math.MinInt, math.MinInt
    for _, n := range nums {
        if n > max1 { 
            if max2 != math.MinInt { max3 = max2 }
            max2 = max1
            max1 = n
        }
        if n > max2 && n < max1 {
            max3 = max2
            max2 = n
        }
        if n > max3 && n < max2 { max3 = n }
    }
    if max3 != math.MinInt { return max3 }
    return max1
}

• This code used math.MinInt(-9223372036854775808)
• Looks complicated becuase first if condition doesn't need to put if condition inside.
• When max2 has math.MinInt, it doesn't need to put max2 to max3.
• Becuase of that i think it made delay.

sample 2900 KB submission

func thirdMax(nums []int) int {

    // DESC
    max := make([]int, 0, 3)
    max = append(max, nums[0])

    for i:=1; i < len(nums); i++ {
        max = add(max, nums[i])
    }

    if len(max) < 3 {
        return max[0]
    }
    return max[2]
}

func add(max []int, m int) []int {
    if len(max) == 1 {
        if m == max[0] {
            return max
        }
        if m > max[0] {
            max = append(max, m)
            max[0], max[1] = max[1], max[0]
        } else { // m < max[0]
            max = append(max, m)
        }
        return max
    }
    if len(max) == 2 {
        if m == max[0] || m == max[1] {
            return max
        }
        if m > max[0] {
            max = append(max, max[1])
            max[0], max[1] = m, max[0]
        } else if m > max[1] {
            max = append(max, max[1])
            max[1] = m
        } else {
            max = append(max, m)
        }
        return max
    }
    // 3 elements already
    if m == max[0] || m == max[1] || m == max[2] {
        return max
    }
    if m > max[0] {
        max[0], max[1], max[2] = m, max[0], max[1]
    } else if m > max[1] {
        max[1], max[2] = m, max[1]
    } else if m > max[2] {
        max[2] = m
    }
    return max
}

• This code made another array named max with 3 lengthes.
• And allocate nums[0] to max.
• Code is so complicated due to so many if conditions with add function.
• When length of max is 1 then just it compares with max[0].
• when length of max is 2 then it compares each max[0] and max[1].
• If not, It will start to make new array by using append.
• When m is bigger then max[0], append max[1](it will have 1st, 2nd-1, 2nd-2 based on size).
• Copy 1st to 2nd-1 and m to 1st.
• It will have 1st, 2nd, 3rd.
• When length is 3, just checking m is same value which array already has.
• And check consecutively.

sample 3000 KB submission

func thirdMax(nums []int) int {
    var first, second, third = math.MinInt64, math.MinInt64, math.MinInt64

    for _, num := range nums {       
        if first == num || second == num || third == num {
            continue
        }
        if num > first {
            third = second
            second = first
            first = num

        } else if num > second {
            third = second
            second = num
        } else if num > third {
            third = num
        }
    }

    if third == math.MinInt64 {
        return first
    }

    return third
}

• I think this code is simple.
• Allocate Minint64 to all variables.
• The continue statement functions to filter using the specified condition as shown in the subheading. Unlike the break statement, the continue statement must be used in connection with the for statement. This is because when the continue statement is encountered, it moves back to the condition check (the beginning of the loop) part of the loop.
• I think this is the main point in this code also optimized solution.