1
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ If it fails because it takes too long to compute the right answer, then please add a time-limit-exceeded tag. However, if it is computing the wrong answer, then this question is off-topic. Please clarify which situation it is. \$\endgroup\$ – 200_success Oct 23 '18 at 6:44
  • \$\begingroup\$ @200_success for this algorithm it fail computing the wrong answer. But only on a special case that I can explain. I have another naive O(n²) algorithm which takes too long. How should I proceed? \$\endgroup\$ – UmNyobe Oct 23 '18 at 7:14
  • \$\begingroup\$ Unfortunately, if there is known to be a case that causes a wrong answer, you'll have to debug that on your own first, because debugging is outside the scope of Code Review. After that, we can proceed to review the code for performance. \$\endgroup\$ – 200_success Oct 23 '18 at 7:17
  • \$\begingroup\$ @200_success updated question. \$\endgroup\$ – UmNyobe Oct 27 '18 at 8:52
  • \$\begingroup\$ The code you posted is incomplete. How is class Solution implemented? What does the function maxProd() look like? \$\endgroup\$ – G. Sliepen Oct 27 '18 at 19:09
0
\$\begingroup\$

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;
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.