O(NlogN) & O(N) solution w/ C++ & Python


  • 0
    Z

    python nlogn solution

    class Solution(object):
        def maximumProduct(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            nums = sorted(nums)
            return max(nums[-1] * nums[-2] * nums[-3], nums[-1] * nums[0] * nums[1])
    
    # 83 / 83 test cases passed.
    # Status: Accepted
    # Runtime: 152 ms
    

    python n solution:

    class Solution(object):
        def maximumProduct(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            n1 = n2 = float('inf')
            m1 = m2 = m3 = float('-inf')
            for n in nums:
                if n >= m1:
                    m1, m2, m3 = n, m1, m2
                elif n >= m2:
                    m2, m3 = n, m2
                elif n > m3:
                    m3 = n
                if n <= n1:
                    n1, n2 = n, n1
                elif n < n2:
                    n2 = n
            return max(n1 * n2 * m1, m1 * m2 * m3)
    
    # 83 / 83 test cases passed.
    # Status: Accepted
    # Runtime: 83 ms
    

    c++ nlogn solution

    class Solution {
    public:
        int maximumProduct(vector<int>& nums) {
            int n = nums.size();
            sort(nums.begin(), nums.end());
            return max(nums[0] * nums[1] * nums[n-1], nums[n-3] * nums[n-2] * nums[n-1]);
        }
    };
    
    // 83 / 83 test cases passed.
    // Status: Accepted
    // Runtime: 72 ms
    

    c++ n solution

    class Solution {
    public:
        int maximumProduct(vector<int>& nums) {
            int n1 = 1001, n2 = 1001, m1 = -1001, m2 = -1001, m3 = -1001;
            for ( int n : nums ) {
                if ( n >= m1 ) {
                    m3 = m2;
                    m2 = m1;
                    m1 = n;
                } else if ( n >= m2 ) {
                    m3 = m2;
                    m2 = n;
                } else if ( n > m3 ) {
                    m3 = n;
                }
    
                if ( n <= n1 ) {
                    n2 = n1;
                    n1 = n;
                } else if ( n < n2 ) {
                    n2 = n;
                }
            }
            return max(n1 * n2 * m1, m1 * m2 * m3);
        }
    };
    
    // 83 / 83 test cases passed.
    // Status: Accepted
    // Runtime: 49 ms
    

Log in to reply
 

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