Python solution with detailed explanation


  • 1
    G

    Solution with detailed discussion https://discuss.leetcode.com/topic/91279/python-solution-with-detailed-explanation

    Array Partition I https://leetcode.com/problems/array-partition-i/#/description

    Editorial https://leetcode.com/articles/array-partitioning-i/

    Bruteforce

    • Find all permutations and then imagine each adjacent pair being pairs.

    Sorting based solution

    1. For an optimized solution, begin with an example arr = [4,3,1,2]
    2. Sort this array. arr = [1,2,3,4]
    3. Now note that 1 needs to be a paired with a larger number. What is the number we would like to sacrifice? Clearly the smallest possible.
    4. This gives the insight: sort and pair adjacent numbers.
    5. Sorting takes Nlg(N) and space lg(N).
    class Solution(object):
        def arrayPairSum(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            nums.sort()
            s_so_far = 0
            for i in range(0, len(nums)-1, 2):
                s_so_far += nums[i]
            return s_so_far
    

    Hashing based solution

    1. We use the same idea to pair adjacent elements, but instead use a counting sort approach.
    2. Range of numbers is -10k to 10k. This means 20001 elements.
    3. Build the frequency map for the input.
    4. Now iterate this map. When frequency is even, the contribution is the implied number times freq//2. When odd, it is (implied number) times (freq//2 + 1).
    5. Implied number: (idx-10000)
    6. The time and space complexity is order K where K is the range of the numbers.
    class Solution(object):
        def arrayPairSum(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            res = [0]*20001
            for x in nums:
                res[x+10000] += 1
            s_so_far, adjust = 0, False
            for idx, freq in enumerate(res):
                if freq:
                    freq = freq-1 if adjust else freq
                    if freq&1:
                        s_so_far += ((freq//2) + 1)*(idx-10000)
                        adjust = True
                    else:
                        s_so_far += ((freq//2))*(idx-10000)
                        adjust = False
            return s_so_far
    

  • 0
    L

    @gabbu Hi, thanks for your answer.
    Just have one question about
    Now note that 1 needs to be a paired with a larger number. What is the number we would like to sacrifice? Clearly the smallest possible.

    Why the 'smallest'? We have no chance to remove the smallest number but largest


Log in to reply
 

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