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<int> out(N);
stack<pair<int, int>> temps;

for (auto i=0; i<N; ++i)
{
    cin >> 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<int> rates(N);
copy_n(istream_iterator<int>(cin), N, begin(rates));
vector<int> 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<int> rates(N);
copy_n(istream_iterator<int>(cin), N, begin(rates));
vector<int> 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<N; ++i)
{
    cout << (indices[i]==-1 ? 0 : indices[i]-i) << " ";
}