Who wants to solve with me a rocket problem? All right 🙂 We might not be rocket scientists but we surely enjoy rocket and mountain problems, especially when they act as cover-up for some computer science subject.

In this case, for those of you seeking the simplest possible method there is a naive approach that can be written in a couple minutes 😉 We will not discuss that. Instead, we are interested in an optimal solution with linear time complexity.

Problem Description:

Discussion:

As we see from the time complexity O(M + N + H) a linear solution is expected. There cannot be any nested loops, recursion or other methods that would make it polynomial or worse. Linear sounds great but how?

Let’s do some logical connections. What we know or can be found easily:

• we know the current landscape configuration, a sequence of heights stored in array A

• based on it we can find the maximum landscape height MAXH

• maybe the landscape contains MAXH more than once, but we only care for the first “peak”

• side note. why we only care for the first peak. if the landscape did contain multiple positions having same height, there is no way for a flying rocket to reach the 2nd or other subsequent peak, without crushing into the first peak.

• we extend this search for all valid heights. so for each height h with 0 <= h <= MAXH we need to find the minimum landscape index MINL(h) = { i | h = A[i] and i is minimum }. • although it contains the maximal value of MAXH, certain landscape inputs might not contain an index for every other possible height in the range [0 .. MAXH] so there might exist such k with 0 <= k <= MAXH where MINL(k) is empty. this possibility obstructs us from using function MINL to forecast the first landscape index where a projectile is going to hit. To cover, we will define another function named MINLC: MINLC(h) = MINL(h), if MINL(h) is not ∅ OR MINLC(h) = smallest, nonempty MINL(h1), where h1 > h, if MINL(h) is ∅

• here is an example. the landscape array contains four positions:
    A[0] = 0, A[1] = 3, A[2] = 3, A[3] = 5.

The MAXH is 5, meaning that MINL contains the following values:

    MINL(0) = 0
    MINL(1) = ∅
    MINL(2) = ∅
    MINL(3) = 1
    MINL(4) = ∅
    MINL(5) = 3

MINLC will be equal to MINL for all non empty positions. For the rest:

MINLC(height value 1) = index value 1, because the index 1 in landscape array A contains the first non-empty value satisfying height value 3 > height value 1

    MINLC(1) = 1
    MINLC(2) = 1
    MINCL(4) = 3

• we should not forget that each rocket crushing into the ground falls at the previous landscape index increasing the local height. we will need to take into account such updates

• due to the MINLC function, for any launch height, we can find directly which is the landscape index where the rocket falls. all we have to do is iterate the B array, find the index where the rocket falls by applying MINLC, then increase ground level at that position.

Code:

• Note. This is a C99 solution focusing on readability rather than code length. Also, it can use better error logging or commenting. These aspects were not the purpose of this solution.

• At this point we achieve the worst case time complexity of O(M + M + H + N) which can be further optimized into O(M + H + N) by introducing some std::map to store the (height, ground index) pairs. This way we eliminate the need for finding the largest height, then allocating memory space. I will leave this small exercise to you 😀

 
struct Results 
{
    int * A1;
    int M;
};
 
struct Results shootingRockets(int A[], int M, int B[], int N)
{
    struct Results r;
    memset(&r, 0, sizeof(r));
 
    if (M < 1 || !A || !B)
        return r;
 
    if (N < 1)
    {
        r.A1 = A;
        r.M = M;
    }
 
    //find max terrain height
    int maxTerrainH = -1;
    int j = 0;
    for (j = 0; j < M; ++j)
    {
        if (A[j] > maxTerrainH)
            maxTerrainH = A[j];
    }
 
    //all rockets will fall before, or fly over
    if (maxTerrainH <= 0)
        return r;
 
    //we are using extra storage space to accomodate
    //the index of the first peak of certain height.
 
    //the heights array will be maxTerrainH + 1 to
    //react correctly to launches from height 0
 
    int heightsCount = maxTerrainH + 1;
 
    int *heights = (int *)malloc(heightsCount * sizeof(int));
    if (!heights)
    {
        return r;
    }
 
    memset(heights, -1, heightsCount * sizeof(int));
 
    //we are building the MINLC function:
 
    //First step. iterate landscape positions,
    //store in heights array, only those indexes
    //with peaks of heights we haven't seen before
 
    int max = -1;
    int k = 0;
    for (k = 0; k < M; ++k)
    {
        if (A[k] > max)
        {
            max = A[k];
            *(heights + max) = k;
        }
    }
 
    //Second step. Some positions are stil storing -1
    //These landscape heights are not accessible
    //at this point through dirrect shots. We need to
    //calculate their heights value based on surrounding
    //heights.
 
    for (k = heightsCount - 1; k > 0; --k)
    {
        if (*(heights + k - 1) == -1)
        {
            *(heights + k - 1 ) = *(heights + k);
        }
    }
 
    //iterate each launch height
 
    for (k = 0; k < N; ++k)
    {
        //rocket flies over horizon?
 
        if (B[k] > maxTerrainH)
        {
            continue;
        }
 
        //find where does it hit ground
 
        int whereItHits = *(heights + B[k]);
        int whereItFalls = whereItHits - 1;
 
        if (whereItFalls >= 0)
        {
            //increase ground level
            A[whereItFalls] += 1;
 
            //before, a rocket would fly over
            //now, due to the latest ground level increase,
            //hits right here. we have to update the heights array
 
            if (*(heights + A[whereItFalls]) > whereItFalls)
            {
                *(heights + A[whereItFalls]) = whereItFalls;
            }
        }
    }
 
    if (heights)
    {
        free(heights);
    }
 
    r.A1 = A;
    r.M = M;
 
    return r;
}