Evolve from brute force to optimal, a review of all solutions


  • 0
    1. O(n^2) brute force
        vector<int> countSmaller(vector<int>& nums) {
            int n=nums.size();
            vector<int> count(n);
            for(int i=0;i<n-1;i++)
                for(int j=i+1;j<n;j++)
                    if(nums[j]<nums[i]) count[i]++;
            return count;
        }
    
    1. O(n^2) Brute force with binary search. We can visit the array from back to beginning. Keep the visited array sorted so that find the insert position is O(logn). However, insert to a sorted array is O(n) so it is still O(n^2) but faster than #1.
        vector<int> countSmaller(vector<int>& nums) {
            int n=nums.size();
            if(!n) return vector<int>();
            vector<int> count(n), vstd(1,nums.back());
            for(int i=n-2;i>=0;i--) {
                auto it = lower_bound(vstd.begin(),vstd.end(),nums[i]);
                count[i]+=it-vstd.begin();
                vstd.insert(it,nums[i]);
            }
            return count;
        }
    
    1. Average O(nlogn), worst O(n^2) binary search tree. Instead of storing the visited numbers in an array, we can store it in a bst. Look up and insert to bst is O(logn) if the bst is balanced. In the worst case where the input array is increasing or decreasing, the bst becomes a link list so lookup and insert take O(n).
        class Node {
            public:
            Node (int val):val_(val),left_(NULL),right_(NULL),lt_(0) {}
            Node *left_,*right_;
            int lt_,val_; // left subtree size
        };
        int insert(int val, Node *rt) {
            int ct=0;
            Node **r = &rt;    
            while(*r)
                if(val<(*r)->val_) {
                    (*r)->lt_++;
                    r=&(*r)->left_;
                } else {
                    ct+=(*r)->lt_+(val>(*r)->val_);
                    r=&(*r)->right_;
                }
            *r = new Node(val);
            return ct;
        }
        void dlt(Node *r) {
            if(!r) return;
            dlt(r->left_);
            dlt(r->right_);
            delete r;
        }
        vector<int> countSmaller(vector<int>& nums) {
            if(nums.empty()) return vector<int>();
            int n=nums.size();
            vector<int> res(n);
            Node *r=new Node(nums[n-1]);
            for(int i=n-2;i>=0;i--) res[i]=insert(nums[i],r);
            dlt(r);
            return res;
        }
    
    1. O(nlogn) binary index tree. The key of BST is the input array value. So it may not be balanced. BIT is built according to the array index so it is guaranteed to be balanced. Here is a great tutorial from geeksforgeeks. If you understand the tutorial, then the next question is how to transform this problem to the getSum problem that can be solved by bit. As in previous solutions, when we visit the number from the end, we want to keep the visited number sorted for efficient lookup. Since BIT is an array and we do not want to insert to a sorted array as in #2, the solution is to allocate an array with sufficient size and put a number to its sorted position. Then counting smaller numbers after a number is equivalent to get the sum till its index in the BIT array which is same as the problem in the tutorial.
        vector<int> countSmaller(vector<int>& nums) {
            vector<int> temp=nums;
            sort(temp.begin(),temp.end());
            unordered_map<int,int> index;
            int n = nums.size();
            for(int i=0;i<n;i++) index[temp[i]]=i+1;
            vector<int> bit(n+1);
            for(int i=n-1;i>=0;i--) {
                int id = index[nums[i]];
                temp[i]=getSum(id-1,bit);
                update(id,bit);
            }
            return temp;
        }
        int getSum(int i, vector<int>& bit) {
            int sum = 0;
            while(i) {
                sum+=bit[i];
                i&=i-1;
            }
            return sum;
        }
        void update(int i, vector<int>& bit) {
            while(i<bit.size()) {
                bit[i]++;
                i+=i&-i;
            }    
        }
    
    1. O(nlogn) merge sort. We can count the inversions during merge sort. When we merge the two sorted arrays, we only need to count the number of elements from the right partition that have been merge. When we merge a number from the left partition, the number of elements before it from the right partition is the count of smaller numbers after it. The great idea is from @lzyfriday.
        vector<int> countSmaller(vector<int>& nums) {
            int n=nums.size();
            vector<int> index(n),count(n);
            iota(index.begin(), index.end(), 0);
            mergeSort(0,n-1,index,count,nums);
            return count;
        }
        void mergeSort(int l, int r, vector<int> &index, vector<int> &count, vector<int>& nums) {
            if(l>=r) return;
            int mid=(r-l)/2+l;
            mergeSort(l,mid,index,count,nums);
            mergeSort(mid+1,r,index,count,nums);
            int countRt=0,i=l,j=mid+1,k=0;
            vector<int> merge(r-l+1);
            while(i<=mid || j<=r)
                if(j>r || (i<=mid && nums[index[i]]<=nums[index[j]])) {
                    merge[k++]=index[i];
                    count[index[i++]]+=countRt;
                } else {
                    merge[k++]=index[j++];
                    countRt++;
                }
            copy(merge.begin(),merge.end(),index.begin()+l);
        }
    
    1. O(n) Bit manipulation. We can also look at the numbers bit by bit. First, we partition the numbers into two groups according to the msb, starting from the last number. If a number belongs to the large group, the numbers in the small group are the smaller numbers after it. The great idea is from @fun4LeetCode.
        vector<int> countSmaller(vector<int>& nums) {
            int n=nums.size();
            vector<int> count(n),index(n);
            for(int i=0;i<n;i++) index[i]=n-1-i;
            recur(nums,index,count,1<<31);
            return count;
        }
        void recur(vector<int> &nums,vector<int> &index,vector<int> &count,unsigned int mask) {
            int n = index.size();
            if(!mask||n<=1) return;
            vector<int> large, small;
            int highbit = mask & (1<<31) ? 0:mask;
            for(int i=0;i<n;i++)
                if((nums[index[i]]&mask)==highbit) {
                    large.push_back(index[i]);
                    count[index[i]]+=small.size();
                } else small.push_back(index[i]);
            recur(nums,small,count,mask>>1);
            recur(nums,large,count,mask>>1);
        }
    

Log in to reply
 

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