Number of NGEs to the right

Optimized Approach

We can reduce the time complexity to find the number of the next greater elements by using merge sort like in the count inversion problem. For a pair of indexes (i, j), if i < j and arr[i] < arr[j], then the number of elements greater than i can be found through j. Let's see the algorithm in detail.

Algorithm

The algorithm is as follows:

1. Create a vector, temp of size n, to store the number of next greater elements for each index. Initialize it with 0.
    
2. Create another vector, v, to store the pair of elements and their original indices. Populate v with elements from a and their indices.
    
3. Call the function mergesort; Inside the merge sort:
   1. Calculate the middle index, mid, if low is less than high.
       
   2. Recursively call the mergesort function for the left and right halves of the subarray.
       
   3. Call the merge function to merge the sorted halves and count the number of the next greater elements.
       
4. Inside the merge function:
   1. Create two arrays, a and b, and copy elements of the left and right halves into them.
       
   2. Iterate through the two arrays and copy the smaller element into the original array.
       
   3. If the element in a is smaller, that is for the case i < j and arr[i] < arr[j], update temp with count size2-j.
       
   4. Do the above steps for the remaining elements of the array a or b.
       
5. Print the next greater elements of the given indices in the query array.

Implementation in C++

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

void merge(vector<pair<int, int> >& v, vector<int>& temp, int low, int mid, int high) {
 
        int size1 = mid - low + 1;
        int size2 = high - mid;
     
        vector<pair<int, int> > a;
        vector<pair<int, int> > b;
     
        for (int i = 0; i < size1; i++) {
            a.push_back(v[i + low]);
        }
     
        for (int i = 0; i < size2; i++) {
            b.push_back(v[i + mid + 1]);
        }
     
        int i = 0, j = 0, k = low;
     
        while (i < size1 && j < size2) {
            if (a[i].first < b[j].first) {
                temp[a[i].second] += size2 - j;
                v[k++] = a[i++];
            }
            else {
                v[k++] = b[j++];
            }
        }
     
        while (i < size1) {
            v[k++] = a[i++];
        }
     
        while (j < size2) {
            v[k++] = b[j++];
        }
    }
    
    void mergesort(vector<pair<int, int> >& v, vector<int>& temp, int low, int high) {
        if (low < high) {
            int mid = low + (high - low) / 2;
            mergesort(v, temp, low, mid);
            mergesort(v, temp, mid + 1, high);
            merge(v, temp, low, mid, high);
        }
    }
    
int main(){ 
    vector<int> a = {1, 3, 6, 5, 8, 9, 13, 4}; 
    int n = a.size();
    
    vector<int> q = {0, 1, 5};
    
    vector<int> temp(n, 0);
    vector<pair<int, int> > v;
        
    for (int i = 0; i < n; i++) {
        v.push_back({ a[i], i });
    }

    mergesort(v, temp, 0, n - 1);
        
    for (int i = 0; i < q.size(); i++) {
        int j = q[i];
        cout<<temp[j]<<" ";
    }
    
    return 0; 
}

You can also try this code with Online C++ Compiler

Run Code

Implementation in Java

import java.util.*;

class Main {
    
    static void merge(List<Map.Entry<Integer, Integer>> v, List<Integer> temp, int low, int mid, int high) {
        int size1 = mid - low + 1;
        int size2 = high - mid;

        List<Map.Entry<Integer, Integer>> a = new ArrayList<>();
        List<Map.Entry<Integer, Integer>> b = new ArrayList<>();

        for (int i = 0; i < size1; i++) {
            a.add(v.get(i + low));
        }

        for (int i = 0; i < size2; i++) {
            b.add(v.get(i + mid + 1));
        }

        int i = 0, j = 0, k = low;

        while (i < size1 && j < size2) {
            if (a.get(i).getKey() < b.get(j).getKey()) {
                temp.set(a.get(i).getValue(), temp.get(a.get(i).getValue()) + size2 - j);
                v.set(k++, a.get(i++));
            } else {
                v.set(k++, b.get(j++));
            }
        }

        while (i < size1) {
            v.set(k++, a.get(i++));
        }

        while (j < size2) {
            v.set(k++, b.get(j++));
        }
    }

    static void mergeSort(List<Map.Entry<Integer, Integer>> v, List<Integer> temp, int low, int high) {
        if (low < high) {
            int mid = low + (high - low) / 2;
            mergeSort(v, temp, low, mid);
            mergeSort(v, temp, mid + 1, high);
            merge(v, temp, low, mid, high);
        }
    }

    public static void main(String[] args) {
        List<Integer> a = Arrays.asList(1, 3, 6, 5, 8, 9, 13, 4);
        int n = a.size();

        List<Integer> q = Arrays.asList(0, 1, 5);

        List<Integer> temp = new ArrayList<>(Collections.nCopies(n, 0));
        List<Map.Entry<Integer, Integer>> v = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            v.add(new AbstractMap.SimpleEntry<>(a.get(i), i));
        }

        mergeSort(v, temp, 0, n - 1);

        for (Integer j : q) {
            System.out.print(temp.get(j) + " ");
        }
    }
}

You can also try this code with Online Java Compiler

Run Code

Output: 

7 6 1

Complexity Analysis

Time Complexity: Since we are using the merge sort approach to find the count of the next greater element for each index, the time complexity is O(n*logn).

Space complexity: The auxiliary space used is O(n) for n elements.

Also Read - Strong number in c

Frequently Asked Questions

What is dynamic programming?

It is the technique to solve a problem by breaking it down into smaller sets of problems and individually handling the smaller problems to achieve the optimal solution.

What are the approaches of dynamic programming?

Top-down and bottom-up are the two types of approaches in dynamic programming.

What is the major advantage of applying dynamic programming?

Dynamic programming is used because it can provide a local as well as a total optimal solution for the problem, which means that it chooses the best solution for the broken down problem part as well as for the overall solution.

Conclusion

In this blog, we discussed the approach to print the number of next greater elements to the right of the given index element.

Check out this problem - Next Smaller Element

Refer to our guided paths on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must have a look at the problems, interview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!