<= 20 lines Java code. Beats 100%!!

• Thanks to @Pepsi's solution of 327. Count of Range Sum. My code below is so similar with the one Pepsi posted here.

@Chidong's solution with BST is really impressive, but I think because it may not be a balanced tree, his solution maybe not strictly O(nlogn), but merge sort can do it with worst case time complexity in O(nlogn), so that my solution could beat 100%. That's just my guess. please let me know if I am wrong.

``````public class Solution {
public int reversePairs(int[] nums) {
if (nums == null || nums.length == 0) return 0;
return mergeSort(nums, 0, nums.length - 1);
}
private int mergeSort(int[] nums, int l, int r) {
if (l >= r) return 0;
int mid = l + (r - l)/2;
int count = mergeSort(nums, l, mid) + mergeSort(nums, mid + 1, r);
int[] cache = new int[r - l + 1];
int i = l, t = l, c = 0;
for (int j = mid + 1; j <= r; j++, c++) {
while (i <= mid && nums[i] <= 2 * (long)nums[j]) i++;
while (t <= mid && nums[t] < nums[j]) cache[c++] = nums[t++];
cache[c] = nums[j];
count += mid - i + 1;
}
while (t <= mid) cache[c++] = nums[t++];
System.arraycopy(cache, 0, nums, l, r - l + 1);
return count;
}
}
``````

• Nice solution, impressive with optimizations

• Same idea of doing sort and count at the same time. Here is my implementation.

``````public class Solution {
int ret = 0;
void helper(int[] nums, int s, int e){
int len = e-s;
if (len <= 1) return;
int mid = s+(len)/2;
helper(nums, s, mid);
helper(nums, mid, e);
int left = s, left2 = s, idx = 0, right = mid;
int[] temp = new int[len];
while (idx < temp.length ) {
if ( ( left < mid && right < e && nums[left] < nums[right]) || (right==e) )
temp[idx++] = nums[left++];
else {
while ( right < e && left2 < mid && (long)nums[left2] <= (long)nums[right]*2l )
left2++;
ret += mid-left2;
temp[idx++] = nums[right++];
}
}
for (int i=s, j=0; i<e; i++, j++)
nums[i]=temp[j];
}

public int reversePairs(int[] nums) {
if (nums==null || nums.length <2) return 0;
helper(nums, 0, nums.length);
return ret;
}
}
``````

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