Solution to a good question on InterviewBit with Problem Statement

maxproduct_interviewBit.cpp

/*Problem Statement::MAXPPROD_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:<ul>

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

*/

/*
Approach::

The question can be easily seen as finding the Next Greater Element (NGE) twice. Once on the left side and 
once on the right side. 
Store them in different arrays and find the max product.

The only thing to note is here is that there are duplicate elements in the array and that needs to be taken 
care of while finding the NGE.

Time - O(n)
Space - O(n) because just an additional stack is used.

*/

#include<bits/stdc++.h>
using namespace std;

int maxSpecialProduct(vector<int> &A) {
    //get the size of vector
	int n = A.size();
    
	vector<int> LeftSpecialValue(n,0),RightSpecialValue(n,0);
    
	//build LeftSpecialValue 
	stack<int> leftCalc;
    leftCalc.push(n-1);
    for(int i = n-2 ;i >= 0 ; i--){
        while(!leftCalc.empty() && A[leftCalc.top()] < A[i]){
            LeftSpecialValue[leftCalc.top()] = i  ;
            leftCalc.pop();
        }
        leftCalc.push(i);
    }
    while(!leftCalc.empty())
    {
        LeftSpecialValue[leftCalc.top()] = 0 ;
        leftCalc.pop();
    }
	
	//build RightSpecialValue
    stack<int> rightCalc;
    rightCalc.push(0);
    for(int i = 1 ;i < n;i++){
        while(!rightCalc.empty() && A[rightCalc.top()] < A[i]){
            RightSpecialValue[rightCalc.top()] = i ;
            rightCalc.pop();
        }
        rightCalc.push(i);
    }
    while(!rightCalc.empty())
    {
        RightSpecialValue[rightCalc.top()] = 0 ;
        rightCalc.pop();
    }
	
	//find max product for LeftSpecialValue and RightSpecialValue
    long long mx = -1;
    for(int i=0;i<n;i++){
        mx=max(mx,LeftSpecialValue[i]*1LL*RightSpecialValue[i]);
    }
    return mx%1000000007;
}