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
- Find all permutations and then imagine each adjacent pair being pairs.
Sorting based solution
- For an optimized solution, begin with an example arr = [4,3,1,2]
- Sort this array. arr = [1,2,3,4]
- 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.
- This gives the insight: sort and pair adjacent numbers.
- 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
- We use the same idea to pair adjacent elements, but instead use a counting sort approach.
- Range of numbers is -10k to 10k. This means 20001 elements.
- Build the frequency map for the input.
- 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).
- Implied number: (idx-10000)
- 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 = *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
@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