solution: Count of smaller Number after self.


  • 0
    K

    Approach 1 (naive) : O(n^2)

    suppose we are given an array {2,3,4,1}.
    Now you have to find the count of smaller number to the right side of number 3 (suppose).
    So to achieve this we can run a loop from to the right side of 3 and we compare each number to the number 3 and count it if the number is smaller else move to next number.
    This approach have time complexity of O(n^2) as for single element up to n numbers of element are compared.

    Approach 2: O(nlog(n))

    Steps :

    1. sort the array and in sorted array, keep the extra information about the actual position of element in original array.
    2. build a segment tree (based on range sum query ) for an array of size (equal to original array), but the segment tree contains zero only. In other word, we can say we build segment tree for an array (size equal to original array) whose all elements are zero.
    3. we utilise the segment tree to check the smaller element to the current element and
      utilise the sorted array to update the segment tree.
      3.1) pick the element (W) from sorted array and check the original index of the element, let say original index is (i).
      3.2) query in segment tree for smaller element in range (i, size), let say size is the length of original array.
      This will give the element count smaller then the picked element (W).
      3.3) update the segment tree for the position(i) to 1, tis means one element placed at the position(i).

    Let arr={2,4,3,1}

    After step 1:
    sorting : Arr = {1,2,3,4}
    original index = {3,0,2,1} //extra array to store original indexes of elements.

    After step 2:
    segment_tree ={ 0,0,0,0,0,0,0 }

    After step 3:
    loop (0 to 3 ) for Arr

    for first iteration , element (W=1) and index (i=3)
    sum_query(segment_tree, i+1,3) => result =0;
    update(segment_tree,i, 1) => segment_tree ={ 1,0,1,0,0,0,1 }

    for second iteration , element (W=2) and index (i=0)
    sum_query(segment_tree, i+1,3) => result =1;
    update(segment_tree,i, 1) => segment_tree ={ 2,1,1,1,0,0,1 }

    for third iteration , element (W=3) and index (i=2)
    sum_query(segment_tree, i+1,3) => result =1;
    update(segment_tree,i, 1) => segment_tree ={ 3,1,2,1,0,1,1 }

    for fourth iteration , element (W=4) and index (i=1)
    sum_query(segment_tree, i+1,3) => result =2;
    update(segment_tree,i, 1) => segment_tree ={ 4,2,2,1,1,1,1 }

    sorting of array will take O(log(n)) time and then each update and sum query take O(long) time, so total complexity of this approach is O(log(n)).


Log in to reply
 

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