Time Limit Exceeded for build_max_heap

Question

This problem is from HackerEarth:

The Monk learned about priority queues recently and asked his teacher for an interesting problem. So his teacher came up with a simple problem. He now has an integer array A. For each index i, he wants to find the product of the largest, second largest and the third largest integer in the range [1,i].

Note: Two numbers can be the same value-wise but they should be distinct index-wise.

Input:

• The first line contains an integer N, denoting the number of elements in the array A.
• The next line contains N space separated integers, each denoting the ith integer of the array A.

Output:

Print the answer for each index in each line. If there is no second largest or third largest number in the array A upto that index, then print "-1", without the quotes.

Constraints:

1 <= N <= 100000
0 <= A[i] <= 1000000

Sample Input

5
1 2 3 4 5

Sample Output

-1
-1
6
24
60

Explanation

There are 5 integers 1,2,3,4 and 5.

• For the first two indexes, since the number of elements is less than 3, so -1 is printed.
• For the third index, the top 3 numbers are 3,2 and 1 whose product is 6.
• For the fourth index, the top 3 numbers are 4,3, and 2 whose product is 24.
• For the fifth index, the top 3 numbers are 5,4 and 3 whose product is 60.

Time Limit: 1.0 sec(s) for each input file.

Memory Limit: 256 MB

Source Limit: 1024 KB

Marking Scheme: Marks are awarded if any testcase passes.

Allowed Languages: C, CPP, CLOJURE, CSHARP, GO, HASKELL, JAVA, JAVASCRIPT, JAVASCRIPT_NODE, LISP, OBJECTIVEC, PASCAL, PERL, PHP, PYTHON, RUBY, R, RUST, SCALA

Here is my solution:

#include <iostream>
#include <limits>

#define lld long long
int n, N = 0;
using namespace std;
void max_heapify(int arr[], int n, int i){
    int largest = i;
    int left = 2 * i;
    int right = 2*i + 1;
    if(left <= n && arr[left] > arr[largest]){
        largest = left;
    }
    if(right <= n && arr[right] > arr[largest]){
        largest = right;
    }
    if(largest != i){
        swap(arr[i], arr[largest]);
        max_heapify(arr, n, largest);
    }
}
void build_max_heap(int arr[], int n){
    for(int i = n/2; i >=1; i--){
        max_heapify(arr,n,i);
    }
}

int extract_max(int arr[], int in){

    if(in < 1){
        throw "underflow";
    }

    int max = arr[1];
    arr[1] = arr[in--];
    max_heapify(arr, in, 1);
    return max;
}

int main(){
    cin >> n;
    int in;
    int *arr = new int[n+100];
    int _1st,_2nd,_3rd;
    for (int i = 1; i <= n; ++i) {
        cin >> arr[i];
        build_max_heap(arr, i);

        lld ans;

        if (i <= 2) {
            cout << "-1" << endl;
        }
        else {
            _1st = extract_max(arr, n);
            _2nd = extract_max(arr, n);
            _3rd = extract_max(arr, n);

            ans = _1st * _2nd * _3rd;
            printf("%lld\n", ans);
            int p = i;
            arr[p] = _1st; p--;
            arr[p] = _2nd; p--;
            arr[p] = _3rd;


        }
    }

    return 0;
}

Here I'm calling the build_max_heap for every input, because the problem demand to produce an output after each input so, I think that's causing the problem, but as far as I know, Heapify takes O(log n) time and build_max_heap takes linear time, so it shouldn't exceed more that one second for the 4th input which is here around 1000000 input.

Answer 1

First of all, it's probably best to realize that a heap isn't particularly useful for this problem as it's specified. It can be used, but it doesn't really contribute much (if anything at all).

If you do use a heap, you want to take the specific properties of a max heap into account. In particular, a heap is arranged so each node is at least as large as any of its descendant nodes. As such, the first node is always the largest. The second largest is one of the second and third. In a typical case, the other of the second and third will be the third largest (and depending on how we insert items into the heap, we can enforce that being the case, which we probably want to do here). This allows us to find the three largest items in the heap without actually removing them from the heap at all.

As to why we don't need to use a heap, and why it doesn't really contribute much: we really only care about the three largest items seen at any given point. That being the case, we can start with the first three. They're clearly the largest seen to that point, so their product is the first (meaningful) output. Then we want to find the smallest of those three. Compare that to the fourth item, and if it's larger, copy it over the smallest of the first three, then print the product of the first three. Repeat that (find smallest, check against next item, get new value if larger, print out product) until we reach the end of the input.

This requires something like four comparisons (and possibly one assignment) per iteration, regardless of the number of inputs. A quick test shows it running in ~400 ms on my machine

At least in theory, this can be further optimized by observing that the smallest of the first three can only change when we add a new (larger) item to the first three. When we read a number and it's smaller than the smallest of the first three, we can print the previous product, throw away the new number, and repeat.

At least in a quick test on my machine, the latter doesn't seem to make a noticeable difference though. This is probably because the actual computation is already fast enough to keep up with the I/O, so speeding the computation up even more makes little (or no) difference. It's also possible, however that with only three numbers to look at, it's just as fast to scan them as it is to decide whether to scan them or not.

Answer 2

Min heap, not max heap

Somewhat paradoxically, this problem can be solved using a min heap instead of a max heap. If you construct a min heap of size 3 from the first three elements, then you can maintain a size 3 heap that contains the largest 3 elements seen so far like this (in pseudocode):

for (e = next array element) {
    if (e > top_of_min_heap) {
        product = (product / top_of_min_heap) * e;
        replace top_of_min_heap with e;
        fix min_heap;
    }
    print product;
}

The advantage of this min heap solution is that it scales well. For example, if the question asked to track the top 100 largest numbers instead of the top 3, this would work better than just using a simple array to track the top numbers. The runtime complexity of this solution is \$O(N * \log M)\$, where \$N\$ is the number of array elements and \$M\$ is the number of largest numbers to track (in your case 3). This is because the "fix min_heap" step in the code above takes \$O(\log M)\$ time.

Zero tracking

One problem with the solution above is that the array elements are allowed to be zero. With that in mind, you can't just simply do:

        product = (product / top_of_min_heap) * e;

because the top of the min heap could be zero and you can't divide by zero. In order to fix this problem, you would need to track the number of zeros in the min heap, in addition to the tracking the product of all non-zero numbers in the heap. If there are any zeros in the heap, you should print 0, otherwise you should print the value of product.