# Array Partitioning I

• Hi, the sorting way is accepted actually.

• Why I can't search this problem in leetcode ?

• I think so~~the sorting way is accepted..
And the second method is actually counting sort.. Am I right?

• my sorting solution got AC and the judge said it beats 100% of the other java solutions...

• The sorting method was accepted for my case too

• Generally speaking, If sort takes O(nlogn) time complexity, it also takes O(logn) space.

• My sorting solution is also ACed.

• My answer is the same as Approach #2

• class Solution {
public:
int arrayPairSum(vector<int>& nums)
{
int n = nums.size();
int max = 0;
sort(nums.begin(), nums.end());
for (int i = 0; i < n - 1; i = i + 2)
{
max += nums[i];
}
return max;
}
};

• class Solution(object):
def arrayPairSum(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums.sort()
n = 0
res = 0
while n < len(nums):
res += nums[n]
n += 2

``    return res``

• class Solution {
public int arrayPairSum(int[] nums) {
Arrays.sort(nums);
int sum = 0;
for(int i=0;i<nums.length;i=i+2) {
sum = sum + Math.min(nums[i], nums[i+1]);
}
return sum;
}
}

• Solution in C

``````/*
* main.c
*
*  Created on: Sep 2, 2017
*      Author: Prakhar Avasthi
*/

/*
* This problem is pretty straightforward, as in this problem we need to make
* n pairs each with 2 numbers from 2n numbers such that sum of min of two numbers
* in each pair is largest.
* basically if we sort the array and sum every odd digit, we will have our answer.
* Problem is easy, I would suggest you to try various sorting algorithm.
* I tried merge sort. In merge sort, there are 2 steps:
* 1. divide array in 2 parts recursively as we need to implement merging in bottom-up fashion
* 2. while merging bottom-up, we will get/make 2 sorted arrays, using some extra space
* we will merge two sorted arrays in 1 extra space array and copy back.
* Here 2 sorted arrays doesn't mean that we will have two actual array,
* we will have one array but we will know two start points and two end points.
* After sorting, a simple loop will fetch the accepted answer.
* */

#include<stdio.h>
#include<stdlib.h>

void merge(int* arr, int start, int mid, int end)
{
int p = start, q = mid+1;
int *temp_arr;
temp_arr = (int *)malloc((end+1)*sizeof(int));
int i=start;

while(p<mid+1 && q<end+1)
{
if(arr[p]<=arr[q])
{
temp_arr[i] = arr[p];
i++; p++;
} else {
temp_arr[i] = arr[q];
i++; q++;
}
}

if(p<=mid)
{
while(p<=mid)
temp_arr[i++] = arr[p++];
}

if(q<=end)
{
while(q<=end)
temp_arr[i++] = arr[q++];
}
for(int j = start; j<=end; j++)
arr[j] = temp_arr[j];
free(temp_arr);
}

void merge_sort(int *arr, int left, int right)
{
if(left == right) return;

int new_right = (left+right)/2;
merge_sort(arr, left, new_right);
merge_sort(arr, new_right+1, right);
merge(arr, left, new_right, right);
}

int arrayPairSum(int* nums, int numsSize) {
int result = 0;

merge_sort(nums, 0, numsSize-1);

for(int i = 0; i < numsSize; i=i+1)
{
printf("%d ",nums[i]);
result = result + nums[i];
}
return result;
}

int main()
{
int arr[10] = {1,-3,5,-4,8,9,-2,0,7,6};

setbuf(stdout, NULL);

printf("%d", arrayPairSum(arr,10));
return 0;
}

``````

• # Solution in Python

``````class Solution(object):
def arrayPairSum(self, nums):
"""
:type nums: List[int]
:rtype: int
"""

nums.sort()
return sum(nums[::2])
``````

• class Solution {
public int arrayPairSum(int[] nums) {
int len=nums.length;
Arrays.sort(nums);
int sum=0;
for(int i=0;i<len/2;i++){
sum+=nums[2*i];
}
return sum;
}
}

• class Solution {
public:
int arrayPairSum(vector<int>& nums) {
sort(nums.begin(),nums.end());
int min=0,output =0;
for(int i=0;i<nums.size();i+=2)
{

``````        int x = nums[i];

output += x;
}
return output;
}
``````

};

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