HackerRank: Find Maximum Index Product ( Stack, DS, Histogram Logic )

HackerRank: Find Maximum Index Product ( Stack, DS )
(Find me on HackerRank @ Handle: BishalG )

Problem Summary:
According to problem, you are given an array A of length n.
For each index - i in the array, calculate IndexProduct(i) which is defined as:
IndexProduct(i) = Left(i) * Right(i). 
Again, Left(i) and Right(i) has following definition:
Left(i) = Index on the left side of the array such that j < i and arr[j] > arr[i]
Right(i) = Index on the right side of the array such that j > i and arr[j] > arr[i]
If such index does not exist then it would be 0 in both cases.
Our task is to find maximum of IndexProduct(i) among all values of i.

Solution Idea:

I'm explaining here the idea for generating values for Left array. Similar concept can be applied to find the values for Right array. After finding both arrays, we can easily calculate IndexProduct for every i and find the maximum value among them which will be our answer.

Calculating Left array:
If we think about naive approach to generate values for Left array, then it would be: Iterate over every index, then for each index, say - i, iterate over the left side of the array with index , say - j, starting from  j = i  - 1 to 0 , and stop iteration whenever we find a index with condition arr[j] > arr[i], such j will be stored in Left(i). If we reached to 0 index and do not meet above condition, we need to store 0 in Left(i) as mentioned in the problem statement.
The sample code for naive calculation of Left array would be like this:

1 2 3 4 5 6 7 8 9 10 11 12 13

void calculateLeft(vector<int>& arr, vector<int>& lft) { int n = arr.size(); lft[0] = 0; for (int i = 1; i < n; ++i) { lft[i] = 0; for (int j = i - 1; j >= 0; --j) { if (arr[j] > arr[i]) { lft[i] = j + 1; break; } } } }

Since, we are fixing n- indices with first for loop ( at line no - 4) and iterating over at most n - indices with second for loop ( at line no - 6), the overall time complexity of our naive approach is : O(n * n).

Can we optimize our naive solution ?
Is there any over calculation in second for loop starting at line number - 7 ?

Lets analyze behavior of looping and comparisons from each index - i over the indices -j in second for loop.
We can notice that, For an index -i :

• It will compare with all element to its left side which are less than or equal to arr[i].
• It will stop comparison as soon as it find j, such that arr[j] > arr[i].

So, the values which do not satisfy condition of line number - 7 are always less than or equal to the value at index - i. Lets assume that , we did all those comparisons for some index - i, and now lets think about doing comparisons for index - (i + 1). There might be two cases:

Case 1.) arr[i + 1] >= arr[i] 

    In this case, from index - (i + 1) , while moving to the left side for doing comparisons, we will meet all those values which we had already met while doing comparison for index - i. It is because, as all those values are less than or equal to value at index - i ( i.e arr[i] ), these values will definitely be less value at index - (i + 1) ( i.e. arr[i + 1] ) since arr[i] <= arr[i  + 1].

We can conclude that if we once do comparison for index - i, we again do not need to do comparison with all those values which we had already did with index -i. So, we can skip all those values while doing comparison to the left side from index - (i + 1) or later.

Case 2.) arr[i + 1] < arr[i]

     This case is obvious, as value at index - i (i.e. arr[i]) is greater than that of value at index - (i + 1) (i.e arr[i + 1]), Left value of index - (i + 1) will be i.

Now, lets concentrate on Case 1, as we concluded there that , for an index - i, once we did some unsatisfactory comparisons with indices in it's left sides, then we no longer need to compare with those set of indices in future.
Hence, if we somehow mark those as removed , we do not need to compare with those indices again in future. So, we will only perform comparison with  those indices which are not marked. Now, we can change our code to as follow:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

void calculateLeft(vector<int>& arr, vector<int>& lft) { int n = arr.size(); lft[0] = 0; vector<bool>removedMark(n, false); for (int i = 1; i < n; ++i) { lft[i] = 0; for (int j = i - 1; j >= 0; --j) { if (removedMark[j] == true) { continue; // we do not need to compare with those indices // which are already removed before } if (arr[j] > arr[i]) { lft[i] = j + 1; break; } removedMark[j] = true; //unsatisfactory comparison } } }

Wait Wait !!
Did we decrease our time complexity efficient than before ?
No, it's still O( n * n ) !! 😟😟
Lets try to optimize our complexity.

Do we really need  "removedMark" ? What about removing all those indices instead of marking ?...Sounds good, right!

We can maintain a stack data-structure to hold all those indices which we need to compare with. In some point of time, at index - i, on the top of stack there will be an index which is nearest one to the left side from index  - i. So, from each index, we will compare with the top element on the stack and removed immediately ( by applying pop operation ) as soon as we notice that the value we will get from the top of the stack is less than or equal to the value at the index - i. After completion of those unsatisfied comparisons  we will add current index - i to the stack.
Hence, from each index -i, we are doing comparisons with only those index which are needed and there is no duplication of comparisons ( i.e. each index is compared with only one index, if comparison is unsatisfactory we will remove immediately and if it is satisfactory we will stop right there). For each index, it is pushed into the stack only once and it is popped out by at most one index, so overall complexity of our stack based solution is reduced to O( n + n ) ⬄ O( n ) !! 😃😄

So our final stack based O( n ) approach for calculating Left array will be like this:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

void calculateLeft(vector<int>& arr, vector<int>& lft) { int n = arr.size(); lft[0] = 0; //according problem definition stack<int>stk; stk.push(0); for (int i = 1; i < n; ++i) { while (stk.size() && (arr[stk.top()] <= arr[i])) { stk.pop(); // poping out all values which are <= current index - i from stack // unsatisfied comparisions are removed at most once!! } if (stk.size() == 0) { lft[i] = 0;//according problem: if no value exists then it would be 0 } else { lft[i] = stk.top() + 1; // value at this index stopped us from popping action, // so this is definitely > arr[i], and "+ 1" for making one indexing !! } stk.push(i); } }

In the similar manner we can calculate Right array and finally combine both of those array to generate IndexProduct which leads us to actual solution of given problem. The full code for given problem is given below.

void calculateLeft(vector<int>& arr, vector<int>& lft) {
     int n = arr.size();
     lft[0] = 0;
     stack<int>stk;
     stk.push(0);
     for (int i = 1; i < n; ++i) {
         while (stk.size() && (arr[stk.top()] <= arr[i])) {
             stk.pop();
         }
         if (stk.size() == 0) {
             lft[i] = 0;
         } else {
             lft[i] = stk.top() + 1; 
         }
         stk.push(i);
     }
}

void calculateRight(vector<int>& arr, vector<int>& rgt) {
    int n = arr.size();
    rgt[n - 1] = 0;
    stack<int>stk;
    stk.push(n - 1);
    for (int i = n - 2; i >= 0; --i) {
        while (stk.size() && (arr[stk.top()] <= arr[i])) {
            stk.pop();
        }
        if (stk.size() == 0) {
            rgt[i] = 0; 
        } else {
            rgt[i] = stk.top() + 1;
        }
        stk.push(i);
    }
}

long long solve(vector<int> arr) {
    int n = arr.size();
    vector<int>lft(n, 0);
    vector<int>rgt(n, 0);
    calculateLeft(arr, lft);
    calculateRight(arr, rgt);
    long long maxIndexProduct = 0;
    for (int i = 1; i < (n - 1); ++i) {
        long long currentIndexProduct =(long long)lft[i] * (long long)rgt[i];
        maxIndexProduct = max(maxIndexProduct, currentIndexProduct);
    }
    return maxIndexProduct;
}

We can apply similar idea to solve following problems.
1.) LightOJ -1083 Histogram
2.) HackerRank Poisonous Plants
3.) Toph: Election In Sylhet City

(Please let me know if you know any other similar problems !!)
(Also, Feel free to share this post if you think that anyone could be beneficial by this!!)
(Any corrections or suggestions or doubts regarding the post will be highly appreciated!!)