LC 561 & LC 628

Solution to LeetCode 561 Array Partition I and LeetCode 628 Maximum Product of Three Numbers

LeetCode 561

Array Partition I (Easy). [link]

Make sure group 1 and group 2 are close so that overall the minimum will be as large as possible. Time complexity O(n log n) (for sorting). Space complexity O(log n).

class Solution(object):
    def arrayPairSum(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        return sum(nums[::2])

LeetCode 628

Maximum Product of Three Numbers (Easy). [link]

There can be negative values, so that the maximum is the multiplication of three max values or the multiplication of the max value and the two smallest negative values. Time complexity O(n log n) and space complexity O( log n).

class Solution(object):
    def maximumProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        return max(nums[-1]*nums[-2]*nums[-3], nums[-1]*nums[0]*nums[1])

Manually find the three maximum and two minimum values. Time complexity O(n). Space complexity O(1).

class Solution(object):
    def maximumProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        max1 = -float("inf")
        max2 = -float("inf")
        max3 = -float("inf")
        min1 = float("inf")
        min2 = float("inf")
        for i in nums:
            if i > max1:                
                max3 = max2
                max2 = max1
                max1 = i
            elif i > max2:
                max3 = max2
                max2 = i
            elif i > max3:
                max3 = i
            if i < min1:
                min2 = min1
                min1 = i
            elif i < min2:
                min2 = i
        return max(max1*max2*max3, max1*min1*min2)

LeetCode 455

Assign Cookies (Easy). [link]

Since we sort twice, time complexity O(m log m + n log n), space complexity O(log n + log m) where n, m are the size of the two arrays.

class Solution(object):
    def findContentChildren(self, g, s):
        """
        :type g: List[int]
        :type s: List[int]
        :rtype: int
        """
        g.sort()
        s.sort()
        gLen = len(g)
        sLen = len(s)
        p1 = p2 = 0
        count = 0
        while p1 < gLen and p2 < sLen:
            while p2 < sLen and g[p1] > s[p2]:
                p2 += 1
            if p2 < sLen:
                count += 1
            p1 += 1
            p2 += 1
        return count