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


  • 4

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

  • 0
    Y

    Nice solution, impressive with optimizations


  • 0

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

Log in to reply
 

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