MAXSPPROD linear algorithm

Question

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 <= N <= 10^5 1 <= A[i] <= 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 <algorithm>
#include <vector>
#include <stack>
#include <iostream>

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

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

void right( std::vector<int>& v, std::vector<int>& r ){
    std::stack<int> stack;

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

int maxProd( std::vector<int>&& v){
    std::vector<int> r(v.size());
    right(v, r);

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

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

int main(){
    std::cout << maxProd({3,2,1,2,3}) << std::endl;
    std::cout << maxProd({1,2,3, 2, 1}) << std::endl;
    std::cout << maxProd({1,2,3, 4, 5}) << std::endl;
    std::cout << maxProd({0, 5, 1, 1, 1, 5}) << std::endl;
    std::cout << maxProd({5, 9, 6, 8, 6, 4, 6, 9, 5, 4, 9}) << std::endl;
        std::cout << maxProd({6, 7, 9, 5, 5, 8 }) << std::endl;
        std::cout << maxProd({1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,0,1}) << 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?

Answer 1

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<int> stack;
for(int i = 0; i < v.size(); ++i){
    int j = next_bigger(v, stack, i );

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

Should be replaced by

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