Small Count

Last Updated on March 25, 2022 by Ria Pathak

CONCEPTS USED:

Binary Search

DIFFICULTY LEVEL:

Hard

PROBLEM STATEMENT(SIMPLIFIED):

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

See original problem statement here

For Example:

Input  : A = [6, 4, 2, 1, 5]

Output : R = [4, 2, 1, 0, 0]

Explanation :   

6 has 4 elements smaller than it on its right i.e. (4, 2, 1, 5)

4 has 2 elements smaller than it on its right i.e. (2, 1)

2 has 1 element smaller than it on its right i.e. (1)

1 has 0 element smaller than it on its right.

5 has 0 element smaller than it on its right.

OBSERVATION:

1. If the value of N is greater than 10^5, a O(N^2) solution will lead to a TLE and a O(N) solution is not possible for this problem, so we should look for a in-between solution.

2. Solving the problem in O(NlogN) would be great, where O(N) would be required for the array traversal only, we are left with O(logN).

3. So this gives us an intuition that may be Binary Search can do our work here.

SOLVING APPROACH:

1. The idea is to use Binary Search.

2. Create an empty vector to store elements in a sorted manner.

3. Start traversing the array from right to left and find the position of the current element in the vector where it should be placed to maintain the sorted property of the vector.

4. Binary Search 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 array for every such element.

5. Print the result array.

SOLUTIONS:

#include <bits/stdc++.h> 
using namespace std; 

/* function for inserting array elements from right to left
 in a sorted manner in a vector and finding count of small
 elements in the array to the right of each element*/
void insert(vector<int> &v, int num, int* res, int i) {

  /* Initialise with start and end index of vector */
  int low = 0;
  int high = v.size() - 1;
  while (low <= high) {

      //finding a mid index  
      int mid = (low + high) / 2;

      //finding value at mid index
      int M = v[mid];

      /* if mid element is greater than or equal to
        num, search in the left half */ 
      if (M >= num) {
          high = mid - 1;
      } else {

      /* else search in the right half also notice low is
        also the count of elements currently less than num */
          low = mid + 1;
      }
  }
  /* therefore low is the index where num should be placed 
    as elements to the left are all less than num*/
  v.insert(v.begin() + low, num);

  /* also indicate the elements less than num in the resultant array */
  res[i] = low;
}

void countSmaller(int *arr, int n) {

    /* resultant array that stores count of lesser elements */
    int res[n] = {0};

    /* vector for determing the position of an element and 
    inserting them accordingly */  
    vector<int> v;
    for (int i = n - 1; i >= 0; i--) {
        insert(v, arr[i], res, i);
    }

    /* print the resultant array */
    for (int i=0; i<n; i++)
      cout<<res[i]<<" ";

}

int main() {
  int t; cin>>t;
  while(t--){
    int n; cin>>n;
    int arr[n];
    for(int i=0; i<n; i++)
      cin>>arr[i];

    countSmaller(arr, n);
    cout<<"\n";
  }
  return 0;
} 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {

        Scanner sc = new Scanner(System.in);
        int t=sc.nextInt();
        while(t-->0)
        {
            int n=sc.nextInt();
            int []arr = new int[n];
            for(int i=0;i<n;i++)
                arr[i]=sc.nextInt();
            List<Integer> nlist=countSmallerBinary(arr);
            for (Integer integer : nlist)
                System.out.print(integer + " ");
            System.out.println();
        }
    }
    private static List<Integer> countSmallerBinary(int[] nums) {
        Integer[] res = new Integer[nums.length];
        List<Integer> list = new ArrayList<>();
        for (int i = nums.length - 1; i >= 0; i--) {
            insert(list, nums[i], res, i);
        }
        return Arrays.asList(res);
    }

    private static void insert(List<Integer> list, int num, Integer[] res, int i) {
        int lo = 0;
        int hi = list.size() - 1;

        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            int M = list.get(mid);
            if (M >= num) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        list.add(lo, num);
        res[i] = lo;
    }
}

Space Complexity: O(1)

This article tried to discuss Binary Search. Hope this blog helps you understand and solve the problem. To practice more problems on Searching you can check out MYCODE | Competitive Programming.