# Find Maximum Index Product

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:

 1  7 6 8 5 7 9 1 

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:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35  int N; cin >> N; vector arr(N), left(N), right(N); copy_n(istream_iterator(cin), N, begin(arr)); stack memoryL, memoryR; auto i=0; auto j=N-1; for (; i(left[i])*right[i]); } cout << maxIndexProd << endl; 

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

 1 2 3  auto maxIndexProd = inner_product(begin(left), end(left), begin(right), 0ll, [](auto l, auto r){ return std::max(l, r); }, [](auto l, auto r){ return (long long)l*r; }); 

Another approach - more convoluted - uses three support arrays:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16  const int Domain = 100000; int a[Domain]{}, s[Domain]{}, l[Domain]{}; int N, m = 0; cin >> N; auto ans = 0ll; for (auto i = 0; i < N; i++) { cin >> a[i]; while (m && a[s[m-1]] < a[i]) ans = max(ans, l[s[--m]]*(long long)(i+1)); while (m && a[s[m-1]] == a[i]) m--; l[i] = m ? s[m-1]+1 : 0; s[m++] = i; } cout << ans; `

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

We've worked on this challenge in these gyms: modena
comments powered by Disqus