O(n) Intuitive Java solution with fully explanation

• See the proof it from:https://discuss.leetcode.com/topic/87206/java-solution-sorting-and-rough-proof-of-algorithm
Ex: For a serious number(6,1,5,2,4,3)
We have to sort the array and the max outcome will be the following:
We have to select 1 from(1,2), 3 from(3,4), 5 from(5,6).

We can use the hash map to do the same effect in O(n) without O(nlogn) sort first.

1.Store every number in a hash map. We store -10000 on index 0 ~~~ 10000 on index 20001.
(index of map: adjusted value of a number, value of map: count of the number)
Ex: map[0] = 100, means -10000 occurs 100 times.

2.Then we start from the index 0 to index 20001.(Same effect as you sort the array itself).

3.I first define that left over means whether previous pair is complete or not.
If not, leftover = true, otherwise.
We only have to consider four cases:

``````public class Solution {
public int arrayPairSum(int[] nums) {

int[] arr = new int[20001];
int lim = 10000;

for (int num: nums)
arr[num + lim]++;

// leftOver means that there is one alone element in the left
// thinks it as already choose one for one pair
// ex: [(2), 2], [(2), 2], (2), leftOver = true;
boolean leftOver = false;
int sum = 0;
for (int i = -10000; i <= 10000; i++) {
int index = i + lim;
// even
if(arr[index] % 2 == 0){
if(leftOver) {
leftOver = true;
sum += (arr[index] / 2) * i;

}
else {
leftOver = false;
sum += (arr[index] / 2) * i;

}
}
// odd
else if(arr[index] % 2 == 1){
if(leftOver) {
leftOver = false;
sum += (arr[index] / 2) * i;

}
else {
leftOver = true;
sum += ((arr[index] + 1) / 2) * i;
}
}
}

return sum;
}
}
``````

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