MAXSPPROD linear algorithm I am working on the MAXSPPROD problem on interviewBit


  You are given an array A containing N integers. The special product of
  each ith integer in this array is defined as the product of the
  following:
  
  LeftSpecialValue: For an index i, it is defined as the index j such
  that A[j]>A[i] (i>j). If multiple A[j]’s are present in multiple
  positions, the LeftSpecialValue is the maximum value of j.
  
  RightSpecialValue: For an index i, it is defined as the index j such
  that A[j]>A[i] (j>i). If multiple A[j]s are present in multiple
  positions, the RightSpecialValue is the minimum value of j.
  
  Write a program to find the maximum special product of any integer in
  the array.
  
  Input: You will receive array of integers as argument to function.
  
  Return: Maximum special product of any integer in the array modulo
  1000000007.
  
  Note: If j does not exist, the LeftSpecialValue and RightSpecialValue
  are considered to be 0.
  
  Constraints 1 &lt;= N &lt;= 10^5 1 &lt;= A[i] &lt;= 10^9


Basically if you see the vector as a chart LeftSpecialValue and RightSpecialValue are values around local minima.

Here is the algorithm I came up with 

#include &lt;algorithm&gt;
#include &lt;vector&gt;
#include &lt;stack&gt;
#include &lt;iostream&gt;

int mult_mod(int i, int j) {
    return ((i%1000000007) * (j%1000000007)) % 1000000007;
}

int next_bigger(std::vector&lt;int&gt;&amp; v, std::stack&lt;int&gt;&amp; stack, int i){
    while(!stack.empty()){
        int j = stack.top();
        if (v[j] &lt;= v[i]){
            stack.pop();
        }
        else{
            stack.push(i);
            return j;
        }
    }
    stack.push(i);
    return 0;
}

void right( std::vector&lt;int&gt;&amp; v, std::vector&lt;int&gt;&amp; r ){
    std::stack&lt;int&gt; stack;

    for(int i = v.size() - 1; i &gt;= 0; --i){
        r[i] = next_bigger(v, stack, i);
        stack.push(i);
    }
}

int maxProd( std::vector&lt;int&gt;&amp;&amp; v){
    std::vector&lt;int&gt; r(v.size());
    right(v, r);

    int mp = 0;
    std::stack&lt;int&gt; stack;
    for(int i = 0; i &lt; v.size(); ++i){
        int j = next_bigger(v, stack, i );

        int mp_i = mult_mod(j, r[i]);
        if (mp &lt; mp_i){
            mp = mp_i;
        }
    }
    return mp;
}

int main(){
    std::cout &lt;&lt; maxProd({3,2,1,2,3}) &lt;&lt; std::endl;
    std::cout &lt;&lt; maxProd({1,2,3, 2, 1}) &lt;&lt; std::endl;
    std::cout &lt;&lt; maxProd({1,2,3, 4, 5}) &lt;&lt; std::endl;
    std::cout &lt;&lt; maxProd({0, 5, 1, 1, 1, 5}) &lt;&lt; std::endl;
    std::cout &lt;&lt; maxProd({5, 9, 6, 8, 6, 4, 6, 9, 5, 4, 9}) &lt;&lt; std::endl;
        std::cout &lt;&lt; maxProd({6, 7, 9, 5, 5, 8 }) &lt;&lt; std::endl;
        std::cout &lt;&lt; maxProd({1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,0,1}) &lt;&lt; std::endl; //20

    }


This code is intended to be O(n) in time and space. 
The algorithm passes all test but 


  might be failing for larger test-cases


I believe it is because I am using an additional vector for RightSpecialValue, which means in worst case twice the size of the input memory.

Can it be improved to use less space?
I finally spotted the error in my submission : I was computing the maximum of left-most * right-most mod 1000000007 while I should have been computing the maximum  of left-most * right-most, then returning its value modulo 1000000007.

In other terms 

int mp = 0;
std::stack&lt;int&gt; stack;
for(int i = 0; i &lt; v.size(); ++i){
    int j = next_bigger(v, stack, i );

    int mp_i = mult_mod(j, r[i]);
    if (mp &lt; mp_i){
        mp = mp_i;
    }
}
return mp;


Should be replaced by 

long long int mp = 0;
std::stack&lt;int&gt; stack;
for (int i = 0; i &lt; v.size(); ++i)
{
    long long int j = next_bigger(v, stack, i);
    long long int mp_i = j * r[i];
    if (mp &lt; mp_i)
    {
        mp = mp_i;
    }
}
return mp % 1000000007;