**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**

- 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 = [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
```