# Party coolness

See the original problem on HackerRank.

## Solutions

This is a variation of the classical problem Next greater element we have tackled here. As in that case, the naive solution consists in using two loops: for each element we find the next greater element. This solution is quadratic because for each element we pay a linear search. The worst case is when the array is sorted in decreasing order.

### Linear online solution based on stack

The most common approach to this kind of problems consists in using a stack to store the “candidate” NGE for all the previous elements. We have discussed this idea here.

Here is an adaptation of that approach for this problem:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18  int N, rate; cin >> N; vector out(N); stack> temps; for (auto i=0; i> rate; while (!temps.empty() && rate > temps.top().second) { auto t = temps.top(); out[t.first] = i - t.first; temps.pop(); } temps.push({i, rate}); } for (auto i : out) cout << i << " "; 

Since this approach does not require storing all the data in advance, we process the input in a streaming fashion.

### An alternative linear solution

An alternative solution consists in iterating the rates backwards while caching the greatest element encountered so far. The main loop has two parts:

• if the current rate is greater than the greatest rate encountered so far, we just update it;
• otherwise, we update the number of elements to wait until encountering a higher rate.

The second part works this way:

• we check subsequent rates until we find one that is higher than the current rate;
• we use the previously calculated values in the output vector to skip ahead in the sequence and to assign the number of rates to the corresponding position in the output vector.
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24  int N; cin >> N; vector rates(N); copy_n(istream_iterator(cin), N, begin(rates)); vector out(rates.size()); int greatest = 0; for (int i = N - 1; i >= 0; --i) { const auto rate = rates[i]; if (rate >= greatest) { greatest = rate; continue; } int days = 1; while (rates[i + days] <= rate) { days += out[i + days]; } out[i] = days; } for (auto i : out) cout << i << " "; 

### Linear solution using an index array

The approach above might be used to design a solution based on an index array (the very same idea discussed here):

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18  int N; cin >> N; vector rates(N); copy_n(istream_iterator(cin), N, begin(rates)); vector indices(N, -1); for (int i = rates.size() - 2; i >= 0; i--) { auto j = i + 1; while (j != -1 && rates[j] <= rates[i]) j = indices[j]; indices[i] = j; } for (auto i=0; i