{"id":9213,"date":"2022-08-26T12:31:33","date_gmt":"2022-08-26T12:31:33","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=9213"},"modified":"2022-09-13T13:45:32","modified_gmt":"2022-09-13T13:45:32","slug":"number-of-nges-to-the-right","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/number-of-nges-to-the-right\/","title":{"rendered":"Number of NGEs to the Right"},"content":{"rendered":"

\"\"<\/p>\n

Problem Statement<\/h4>\n

You will be given an array of N integers. You will also be given an Integer Q denoting the number of queries.
\nThen, you will have Q queries denoting the indices of the array. You have to return Q integers for those Q queries depicting the number of elements that are greater than the index mentioned in the query and are to the right of the index in the array<\/a> i.e. Number of NGEs to the Right where NGE stands for \u201cNext Greater Element\u201d<\/strong>.<\/p>\n

Example<\/h4>\n

Let us take an array and the queries as shown below
\n\"\"
\nQ=2 , means 2 queries.
\nLet us say they are 2 and 1.<\/p>\n

    \n
  1. For index =2, answer is 2, because there are two elements in right of index 2 with value greater than array[2]=4 {6 and 7}<\/li>\n
  2. For index =1, answer is 0, because there is no element on right of index 1 with value greater than array[1] = 9.<\/li>\n<\/ol>\n

    Also, you might notice that the count of NGEs to the right of the element present at the last index in the array will always be 0. This is because there will not be any element at the right of it and thus NGEs to its right won\u2019t exist.<\/p>\n

    Approach (Brute Force)<\/h3>\n

    The approach is very simple. Let us consider the array shown below and let us say we want to find the number of next greater elements for index 2.<\/p>\n

    \"\"<\/p>\n

      \n
    • Let us keep a counter variable initialised to 0. <\/li>\n
    • Let us also keep a variable (pointer) i at index = query index + 1. <\/li>\n
    • So, we keep i at index = 3.<\/li>\n
    • Now, iterate till we reach the end of the array and for each index, if array[i] > array[query index], then increment the value of the counter variable. <\/li>\n<\/ul>\n

      This is how one query will be solved. Since there are multiple queries, we have to repeat this procedure for all those queries where each query can have a different index.<\/p>\n

      The image below shows the dry run for one Query where index = 2.<\/p>\n

      \"\"<\/p>\n

      So, two elements were found greater than array[2] = 4, which are array[3] = 6 and array[5] = 7. So, the answer to this query is 2.<\/p>\n

      The same procedure will be followed for any other query as well.<\/p>\n

      Corner Case<\/strong>: If the query index = size of the array -1, in this case, we will not iterate as i+1 will not be less than the size of the array rather it will be equal to it. So, the counter will remain 0 only and without iterating, we will get the answer correctly.<\/p>\n

      Now that we have understood the procedure, let us write the code for the same.<\/p>\n

      Code Implementation:<\/h3>\n\t\t\t\t\t\t