Fastest way to find minimal product of 2 array elements containing 200000+ elements

Question

I have an array a[n]. The number n is entered by us. I need to find the minimal product of a[i] and a[j] if:

1) abs(i - j) > k

2) a[i] * a[j] is minimised

Here is my solution (very naive):

#include <iostream>
using namespace std;
#define ll long long
int main() {
    ll n,k; cin >> n >> k;

    ll a[n]; for(ll i=0;i<n;i++) cin >> a[i];

    ll mn; bool first = true;

    for(ll i=0;i<n;i++) {
        for(ll j=0;j<n;j++) {
            if(i!=j)
            if(abs(i-j) > k) {
                if(first) {
                    mn = a[i]*a[j];
                    first = false;
                } else if(a[i]*a[j] < mn) mn = a[i]*a[j];
            }
        }
    }
    cout << mn << endl;
}

But I want to know if there is any faster way to find a minimal product with distance?

Answer 1

Assuming there is at least one pair of elements satisfying the conditions and no multiplication of two elements in it overflows, this can be done in Theta(n-k) time and Theta(1) space worst- and best-case, with something like this:

auto back_max = a[0];
auto back_min = a[0];
auto best = a[0]*a[k+1];

for(std::size_t i=1; i<n-(k+1); ++i) {
    back_max = std::max(back_max, a[i]);
    back_min = std::min(back_min, a[i]);
    best = std::min(best, std::min(a[i+k+1]*back_max, a[i+k+1]*back_min));
}

return best;

This is optimal in terms of asymptotic worst-case complexity for both time and space because the optimal product may be a[0] with any of the n-(k+1) elements in distance at least k+1, so at least n-(k+1) integers need to be read by any algorithm solving the problem.

---

The idea behind the algorithm is as follows:

The optimal product uses two elements of a, assume these are a[r] and a[s]. Without loss of generality we can assume that s > r since the product is commutative.

Due to the restriction abs(s-r) > k this implies that s >= k+1. Now s could be each of the indices satisfying this condition, so we iterate over these indices. That is the iteration over i in the shown code, but it is shifted by k+1 for convenience (doesn't really matter). For each iteration we need to find the optimal product involving i+k+1 as largest index and compare it with the previous best guess.

The possible indices to pair i+k+1 with are all indices smaller or equal i due to the distance requirement. We would need to iterate over all of these as well, but that is unnecessary because the minimum of a[i+k+1]*a[j] over j at fixed i is equal to min(a[i+k+1]*max(a[j]), a[i+k+1]*min(a[j])) due to monotonicity of the product (taking the minimum with respect to both the minimum and maximum over a[j] accounts for the two possible signs of a[i+k+1] or equivalently the two possible directions of monotonicity.)

Since the set of a[j] values over which we optimize here is just {a[0], ..., a[i]}, which simply growths by one element (a[i]) in each iteration of i, we can simply keep track of max(a[j]) and min(a[j]) with single variables by updating them if a[i] is larger or smaller than the previous optimal values. This is done with back_max and back_min in the code example.

The first step of the iteration (i=0) is skipped in the loop and instead performed as initialization of the variables.

Answer 2

Not sure about fastest.

For the simpler problem without i < j - k, the minimal product is among the products of pairs from the two smallest and largest elements.

So, (the following is too complicated, see walnut's answer)
( • balk if k ≤ n
  • initialise minProduct to a[0]*a[k+1])

• keep two dynamic minmax data structures upToI and beyondIplusK
  starting with { } and { a[j] | k ≤ j }
• for each i from 0 to n - k - 1
  • add a[i] to upToI
  • remove a[i+k] from beyondIplusK
  • check for new minimal product among
    min(upToI)×min(beyondIplusK), min(upToI)×max(beyondIplusK),
    max(upToI)×min(beyondIplusK) and max(upToI)×max(beyondIplusK)