Java solution using counting sort


  • 0
    Z

    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;
    }
    

    }

    '''


Log in to reply
 

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