Find Maximum Index Product

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<int> arr(N), left(N), right(N);
copy_n(istream_iterator<int>(cin), N, begin(arr));

stack<int> memoryL, memoryR;
auto i=0; auto j=N-1;
for (; i<N; ++i, --j)
{
    while (!memoryL.empty() && arr[memoryL.top()-1] <= arr[i])
        memoryL.pop();
    
     while (!memoryR.empty() && arr[memoryR.top()-1] <= arr[j])
        memoryR.pop();

    if (memoryR.empty())
        right[j] = 0;
    else  
        right[j] = memoryR.top();
    
    if (memoryL.empty())
        left[i] = 0;
    else  
        left[i] = memoryL.top();

    memoryL.push(i+1);
    memoryR.push(j+1);
} 

auto maxIndexProd = 0ll;
for (i=0; i<N; ++i)
{
    maxIndexProd = max(maxIndexProd, static_cast<long long>(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<usize> = vec![0; n];

    // contains the values of Right
    let mut right: Vec<usize> = 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<usize> = Vec::new();

    // keeps track of the latest elements that are smaller than the current one
    // (from right to left)
    let mut right_stack: Vec<usize> = Vec::new();

    let mut i = 0;
    let mut j = n - 1;

    let remove_smaller_elements = |stack: &mut Vec<usize>, 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).

stack