Solution by draak_krijger


  • 0
    D

    Approach #1 Brute Force [Time Limit Exceeded]

    Intuition

    For each number we check all numbers next to it and count how many numbers are less than it.

    Algorithm

    Suppose our total element is $$N$$. We declare a vector of size $$N$$ (let's call it ans) and initialize it with zero(0). For each position $$i$$ we iterate all position $$j$$ such that $$j>i$$ and increase ans[i] if and only if $$nums[i]>nums[j]$$. Then we return ans vector.

    C++

    class Solution 
    {
    public:
        vector<int> countSmaller(vector<int>& nums) 
        {
            int siz = nums.size() ;
            vector<int> ans(siz) ;
            for(int i=siz-1 ; i>=0 ; i--)
            {
            	ans[i] = 0 ;
            	for(int j=i+1 ; j<siz ; j++)
            	{
            		if(nums[j]<nums[i])
            			ans[i]++;
            	}
            }
            return ans ;
        }
    };
    

    Complexity Analysis

    • Time complexity : $$O(N^2)$$. For each $$i$$ we iterate all $$j (j>i)$$ of the given array. so when $$i = 0$$ then we iterate $$N-1$$ element , for $$i = 1$$ we iterate $$N-2$$ element and so on.... So, Our total complexity $$= \sum_{i=1}^{N-1}i$$ , which is $$O(N^2)$$.

    • Space complexity : $$O(N)$$. We just need a ans vector to store result.


    Approach #2 Merge Sort [Accepted]

    Intuition

    We can use here merge sort technique. In merge sort we apply divide and conquire. At first we divide the array recursively then merge two sorted segment in linear time and make this segment also sorted. For Learning merge sort you can see this.

    Here, we see how two sorted array can merge into a sorted array in linear time. Let we have two sorted array [1,3,5,7] , [2,4,6,8] and we called them firstArray , secondArray respectively. We save our final sorted array in finalArray. Let id1 and id2 are two variable which value indicate how many element from firstArray and secondArray are saved in finalArray respectively.

    Now, if $$firstArray[id1] < secondArray[id2]$$ , then we add $$firstArray[id1]$$ in finalArray and increase id1. Otherwise $$secondArray[id2]$$ in finalArray and increase id2. In this way we get our sorted finalArray in linear time.

    For solving this problem we need pair array. First element of a pair is value of it and second element is index in initial array of this element. When we merge two sub-segment of a segment and firstArray element will be add to finalArray then we add id2(how many element of secondArray already added to finalArray) to count[firstArray[id1].second]. Finally count is our expected result array.

    Algorithm

    We use a recursive function to solve this problem. Let's call it merge_sort. It takes five arguments. Below we describe about each argument

    nums -> It's a pair array which first element is value and second element is initial position of this value.
    sortedArray -> This is an auxiliary array. We use it to sort two subsegment in linear time.
    fans -> This is our ans array.
    l -> Starting Position of this segment.
    r -> Ending Position of this segment.

    At first we solve small portion and merge them. When we merge two sub-segment , we calculate ans (approach of calculating ans is described in Approach).

    C++

    class Solution 
    {
    public:
    	void merge_sort(vector< pair<int,int> >& nums,vector< pair<int,int> >& sortedArray,vector<int>& fans,int l,int r)
    	{
    		if(l == r)
    		{
    			sortedArray[l] = nums[l] ;
    			return ;
    		}
    
    		int mid = (l+r)/2 , id1 , id2 ;
    
    		merge_sort(nums,sortedArray,fans,l,mid);
    		merge_sort(nums,sortedArray,fans,mid+1,r);
    
    		id1 = l ;
    		id2 = mid+1 ;
    
    		for(int i=l ; i<=r ; i++)
    		{
    			if(id1<=mid && id2<=r)
    			{
    				if(nums[id1].first<=nums[id2].first)
    				{
    					sortedArray[i] = nums[id1] ;
    					fans[nums[id1].second] += (id2-mid-1) ;
    					id1++;
    				}
    
    				else
    				{
    					sortedArray[i] = nums[id2] ;
    					id2++;
    				}
    			}
    
    			else if(id1<=mid)
    			{
    				sortedArray[i] = nums[id1] ;
    				fans[nums[id1].second] += (id2-mid-1);
    				id1++;
    			}
    
    			else
    			{
    				sortedArray[i] = nums[id2] ;
    				id2++;
    			}
    		}
    
    		for(int i=l ; i<=r ; i++)
    			nums[i] = sortedArray[i] ;
    	}
    
        vector<int> countSmaller(vector<int>& nums) 
        {
            int siz = nums.size() ;
    
            vector<int> fans(siz) ;
            vector< pair<int,int> > sortedArray(siz) , numArray(siz) ;
    
            if(siz == 0)
            	return fans ;
    
            for(int i=0 ; i<siz ; i++){
            	fans[i] = 0 ;
            	numArray[i] = make_pair(nums[i],i);
            }
    
            merge_sort(numArray,sortedArray,fans,0,siz-1);
    
            return fans ;
        }
    };
    

    Complexity Analysis

    • Time complexity : $$O(nlogn)$$. Maximum depth of merge sort tree will be $$logn$$ and at each depth we traverse whole array which has $$n$$ elements.

    • Space complexity : $$O(n)$$. As we use just use two array of length $$n$$ for solve and one array of length $$n$$ to store array, so our total Space Complexity $$O(n)$$.


Log in to reply
 

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