Accepted C++ Solution using Segment Tree


  • 1
    R

    This problem is solved in following manner,

    • i) Sort values in ascending order keeping track of index and forget
      about the values.
    • ii) Get a index and search from segment tree giving range.
    • iii) Insert that index into the segment tree.

    Solution is given below:

    class Node
    {
    public:
    	int iVal;
    	int iIndx;
    };
    
    class Solution {
    public:
        int tree[100000];
        Node inp[25000];
        
        static bool cmp(Node n1, Node n2)
        {
     	    if (n1.iVal == n2.iVal)
    		    return n1.iIndx<n2.iIndx;
    	    else return n1.iVal<n2.iVal;
    
        }
    
        void update(int node, int left, int right, int indx)
        {
    	    if (indx<left || right<indx) return;
    	    if (left <= indx && indx <= right)
    	    {
    		    tree[node]++;
    	    }
    	    if (left == right) return;
    	
    	    int mid = (left + right) / 2;
    	    update(node * 2, left, mid, indx);
    	    update(node * 2 + 1, mid + 1, right, indx);
    
    	
        }
    
    
        int query(int node, int left, int right, int i, int j)
        {
     	    if (i>right || j<left) return 0;
    
    	    if (i <= left && j >= right) return tree[node];
    
    	    int mid = (left + right) / 2;
    
    	    int ret = 0;
    	    ret = ret + query(node * 2, left, mid, i, j);
    	    ret = ret + query(node * 2 + 1, mid + 1, right, i, j);
    	    return ret;
        }
        vector<int> countSmaller(vector<int>& nums) 
        {
            for (int i = 0; i<nums.size(); i++)
    	    {
    		    inp[i + 1].iVal = nums[i];
    		    inp[i + 1].iIndx = i + 1;
    	    }
    
    	    sort(&inp[1], &inp[nums.size() + 1], cmp);
    
    
    
    	    for (int i = 0; i <= nums.size() * 4; i++) tree[i] = 0;
    	    vector<int> ans;
    	    ans.resize(nums.size(), 0);
    
    	    for (int i = 0; i<nums.size(); i++)
    	    {
    
    		    ans[inp[i + 1].iIndx - 1] = query(1, 1, nums.size(), inp[i + 1].iIndx, nums.size());
    		    update(1, 1, nums.size(), inp[i + 1].iIndx);
    	    }
    
    	    return ans;
    
        }
    };

  • 0
    R

    This solution takes 52ms


  • 0
    Y

    thank you for your key observation "forget about the values". My thoughts becomes much clear.


Log in to reply
 

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