See the original problem on HackerRank.
Solutions
Jotting down a brute force solution is easy but inefficient. The problem can be solved efficiently only by implementing a strategy to skip unnecessary checks.
One solution uses two stacks and two support arrays:
 stack
memoryL
keeps track of the latest elements that are smaller than the current one (from left to right)  stack
memoryR
keeps track of the latest elements that are smaller than the current one (from right to left)  array
left
contains the values of \(Left\)  array
right
contains the values of \(Right\)
Think about how to construct the left
array.
For example:


We read 7
and, since it’s the first element, left[0] = 0
. We push it on to the stack.
Then we read 6
and we check it agains the top of the stack. 7
is there! It means that the leftmost element bigger than 6
is 7
(we actually use the stacks to keep track of the indexes but the point should be clear).
Thus, left[1] = 7
. We push 6
on to the stack.
The next element is 8
. We check it against the top of the stack but 6
is lower. We pop 6
from the stack. We check against the stack and 7
is there. It’s lower than 8
too. We pop it too. The stack is not empty. This means that left[2] = 0
.
We push 8
on to the stack.
The next element is 5
that is lower than the top of the stack so we have left[3] = 8
. We push 5
on to the stack.
We read 7
that is greater than the top of the stack (5
). We pop the latter out. We find 8
that is greater than 8
. Even left[4]
is 8
.
We push 7
on to the stack.
Did you get it? left[5] = 0
and left[6] = 9
.
right
is constructed similarly but…backwards!
Finally, we calculate the product between left
and `right.
Here is a C++ implementation:


Calculating the product can be replaced with inner_product
(or trasform_reduce
):


Another approach  more convoluted  uses three support arrays:


Left to the reader, another accepted solution consists in using an ordered data structure (e.g. treebased set).