# Java solution using counting sort

• Since we need to provide the max sum of the available pairs, i solved it as below:

1. sort using 'Count Sort';
2. loop over the sorted array and sum the numbers in the even array index.
note:the sum of odd numbers will represent the min of the pairs.
Code:
'''
import java.util.Arrays;

public class Partition {

``````public static void main(String[] args) {

int[] intArray = { 1, 4, 3, 2 };
Partition p = new Partition();
System.out.println("solution: "+p.arrayPairSum(intArray));

}

public int arrayPairSum(int[] nums) {
if (nums == null)
return 0;

/** Sort the array using counting sort, as we have integer array **/
nums = countingSort(nums);
System.out.println("sorted array: " + Arrays.toString(nums));
int sum = 0;
for (int i = 0; i < nums.length; i += 2)
sum += nums[i];
return sum;
}

public int[] countingSort(int[] arr) {
int arrayLength = arr.length;
if (arrayLength == 0)
return null;
/** find maximum and minimum values **/
int max = arr[0], min = arr[0];
for (int i = 1; i < arrayLength; i++) {
if (arr[i] > max)
max = arr[i];
if (arr[i] < min)
min = arr[i];
}
int range = max - min + 1;

int[] count = new int[range];
/** initialize the occurrence of each element in the count array **/
for (int i = 0; i < arrayLength; i++)
count[arr[i] - min]++;
/** calculate sum of indexes **/
for (int i = 1; i < range; i++)
count[i] += count[i - 1];
/** modify original array according to the sum count **/
int j = 0;
for (int i = 0; i < range; i++)
while (j < count[i])
arr[j++] = i + min;

return arr;
}
``````

}

'''

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