# Python solution with detailed explanation

• 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

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
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)
else:
s_so_far += ((freq//2))*(idx-10000)