{"id":1598,"date":"2020-07-01T09:31:01","date_gmt":"2020-07-01T09:31:01","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1598"},"modified":"2022-03-25T11:40:40","modified_gmt":"2022-03-25T11:40:40","slug":"small-count","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/small-count\/","title":{"rendered":"Small Count"},"content":{"rendered":"

\"\"<\/p>\n

CONCEPTS USED:<\/h3>\n
\n

Binary Search<\/p>\n<\/blockquote>\n

DIFFICULTY LEVEL:<\/h3>\n
\n

Hard<\/p>\n<\/blockquote>\n

PROBLEM STATEMENT(<\/code>SIMPLIFIED)<\/code>:<\/h3>\n
\n

Given an array A<\/code> containing N<\/code> elements, construct a new array countSmaller[]<\/code> such that countSmaller[i]<\/code> contains count of smaller elements on right side of each element A[i]<\/code> in the array where (0 <= i < N)<\/code>.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

For Example:<\/h4>\n
Input  : A = [6, 4, 2, 1, 5]\n\nOutput : R = [4, 2, 1, 0, 0]\n\nExplanation :   \n\n6 has 4 elements smaller than it on its right i.e. (4, 2, 1, 5)\n\n4 has 2 elements smaller than it on its right i.e. (2, 1)\n\n2 has 1 element smaller than it on its right i.e. (1)\n\n1 has 0 element smaller than it on its right.\n\n5 has 0 element smaller than it on its right.<\/code><\/pre>\n
OBSERVATION:<\/h3>\n
\n
    \n
  1. \n
    If the value of N<\/code> is greater than 10^5<\/code>, a O(N^2)<\/code> solution will lead to a TLE<\/code> and a O(N)<\/code> solution is not possible for this problem, so  we should look for a in-between solution.  <\/p>\n<\/li>\n
  2. \n
    Solving the problem in O(NlogN)<\/code>  would be great, where O(N)<\/code> would be required for the array traversal only, we are left with O(logN)<\/code>.<\/p>\n<\/li>\n
  3. \n
    So this gives us an intuition that may be Binary Search<\/code> can do our work here.<\/p>\n<\/li>\n<\/ol>\n<\/blockquote>\n
    SOLVING APPROACH:<\/h3>\n
    \n
      \n
    1. \n
      The idea is to use Binary Search<\/code>.  <\/p>\n<\/li>\n
    2. \n
      Create an empty vector to store elements in a sorted manner.<\/p>\n<\/li>\n
    3. \n
      Start traversing the array from right<\/code> to left<\/code> and find the position of the current element in the vector where it should be placed to maintain the sorted property of the vector.   <\/p>\n<\/li>\n
    4. \n
      Binary Search<\/code> will be used to find such position. Then insert the element at that position and the position itself will tell the elements smaller than the current element in the vector as it is already sorted. Store this value in a result<\/code> array for every such element.<\/p>\n<\/li>\n
    5. \n
      Print the result<\/code> array.<\/p>\n<\/li>\n<\/ol>\n<\/blockquote>\n
      SOLUTIONS:<\/h3>\n
      \t\t\t\t\t\t