15 ms accepted java soln using mergesort


  • 1
    Z

    Counting smaller on right is much easier as we just need to count how many time we are taking smaller element from right partition during merge of the merge sort process. Once we get an element from left partition that means that smaller on right for current element is the count so far.

    So, With a simple modification of the merge sort code we can calculate smaller on right. The modification involves updating a rank array for the index of the array instead of modifying the array itself and counting smaller while taking element from right during merge. Overall complexity O(nlgn).

    public class Solution {
        public List<Integer> countSmaller(int[] nums) {
            int n = nums.length;
    		int[] rank = new int[n];
    		List<Integer> count = new ArrayList<Integer>(n);
    		
    		if(n == 0){
    		    return count;
    		}
    		
    		for(int i = 0; i < n; i++){
    		    count.add(0);
    			rank[i] = i;
    		}
    		
    		countSmallerOnRightWithMerge(nums, rank, 0, n-1, count);
    		
    		return count;
        }
        
        public void countSmallerOnRightWithMerge(int A[], int rank[], int p, int r, List<Integer> count){
    		if(A.length == 1){
    			return;
    		}
    		
    		if(p < r){
    			int q = (p+r)/2;
    			//sort left side and count ic
    			countSmallerOnRightWithMerge(A, rank, p, q, count);
    			//sort right side and count ic
    			countSmallerOnRightWithMerge(A, rank, q+1, r, count);
    			//merge left and right and count cross ic
    			mergeToCountSmallerOnRight(A, rank, p, q, r, count);
    		}
    	}
    	
        public void mergeToCountSmallerOnRight(int A[], int rank[], int p, int q, int r, List<Integer> count){
    		int n = r-p+1;
    		int i = p;
    		int j = q+1;
    		int mid = q;
    		int k=0;
    		int mergedRank[] = new int[n];
    		int smallerCount = 0;
    		while(i <= mid && j <= r){
    			//satisfies i<j, A[i]<A[j] -- so count smaller on right
    			if(A[rank[i]] <= A[rank[j]]){
    				count.set(rank[i], count.get(rank[i])+smallerCount);
    				mergedRank[k++] = rank[i++];
    			}
    			//i<j, A[i]>=A[j]
    			else{
    				smallerCount++;
    				mergedRank[k++] = rank[j++];
    			}
    		}
    		
    		//copy leftovers from the two partitions into merge
    		while(i <= mid){
    		    count.set(rank[i], count.get(rank[i])+(r-q));
    			mergedRank[k++] = rank[i++];
    		}
    		while(j <= r){
    			mergedRank[k++] = rank[j++];
    		}
    		
    		//update rank
    		System.arraycopy(mergedRank, 0, rank, p, n);
    	}
    }

Log in to reply
 

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