Fight for Laddus

Tuntun mausi challenged Bheem and his team to solve a problem. Raju, Chutki, and Bheem are trying to solve this problem but are unable to do so. As you are a good friend of Raju, he asks for your help.

Given an array, For each element find the value of the nearest element to the right which is having a frequency greater than that of the current element. If there does not exist an answer for a position, then print '-1'

Please help Raju and his team to solve this problem to get the Laddus.

Example:

Input: n = 10, arr = {1, 3, 7, 2, 5, 1, 4, 2, 1, 5}
Output: -1 2 2 1 1 -1 2 1 -1 -1

Approach

C++

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

void fightForLaddus(int n, vector<int> &arr)
{
    vector<int> v(100005, 0);
    vector<pair<int, int>> element;
    vector<int> ans(n);
    for (int i = 0; i < n; ++i)
    {

        element.push_back(make_pair(arr[i], i));
        v[arr[i]]++;
    }
    stack<pair<int, int>> a;
    for (int i = 0; i < n; ++i)
    {
        while (!a.empty() &&
               v[a.top().first] <
                   v[element[i].first])
        {
            ans[a.top().second] = element[i].first;
            a.pop();
        }
        a.push(element[i]);
    }
    while (!a.empty())
    {
        ans[a.top().second] = -1;
        a.pop();
    }

    for (auto &&i : ans)
    {
        cout << i << " ";
    }
    cout << "\n";
}
int main()
{

    int n = 10;
    vector<int> arr = {1, 3, 7, 2, 5, 1, 4, 2, 1, 5};

    fightForLaddus(n, arr);

    return 0;
}