# 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; }); 

A similar approach in Rust.

  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 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50  fn solve(arr: &[usize]) -> usize { let n = arr.len(); // contains the values of Left let mut left: Vec = vec![0; n]; // contains the values of Right let mut right: Vec = vec![0; n]; // keeps track of the latest elements that are smaller than the current one // (from left to right) let mut left_stack: Vec = Vec::new(); // keeps track of the latest elements that are smaller than the current one // (from right to left) let mut right_stack: Vec = Vec::new(); let mut i = 0; let mut j = n - 1; let remove_smaller_elements = |stack: &mut Vec, index: usize| { while let Some(&x) = stack.last() { if arr[x - 1] <= arr[index] { stack.pop(); } else { break; } } }; while i < n { remove_smaller_elements(&mut left_stack, i); remove_smaller_elements(&mut right_stack, j); right[j] = right_stack.last().copied().unwrap_or_default(); left[i] = left_stack.last().copied().unwrap_or_default(); left_stack.push(i + 1); right_stack.push(j + 1); i = i.saturating_add(1); j = j.saturating_sub(1); } left.iter() .zip(right.iter()) .map(|(l, r)| l * r) .max() .unwrap_or(0) } 

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