SUBMIN-Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Lalit Kundu
Tester: Hiroto Sekido, Gerald Agapov
Editorialist: Ajay K. Verma

DIFFICULTY:

Easy

PREREQUISITES:

Ad-hoc, Stack

PROBLEM:

Given an array A of size N, support the following query: for a given x find the number of subarrays whose minimum element is x.

QUICK EXPLANATION:

Preprocess the given array, to compute another array/map B, such that B[x] is the number of subarrays whose minimum element is x. The limit of N is very small. Hence, preprocessing step be done by iterating through all O (N2) subarrays. For each subarray compute its minimum y, and increment B[y]. The queries can be answered easily using the array B.

EXPLANATION:

The number of queries in this problem is bounded by 10, so ideally one should not bother about any preprocessing. However, we explain here how to solve the problem if the number of queries is large.

The idea is to preprocess the original array A to create a new array B such that B[x] represents the number of subarrays of A whose minimum element is x. It is easy to see that once we have this array B, the queries can be answered in O (1) time.

Note that the elements of A are bounded by 106, hence the size of the array B will also be 106. If the elements of A were not bounded, then we would have used a map instead of the array. Next, we discuss how to compute the array B.

An O (N2) algorithm:

In this section we discuss a very naive way of computing B. We iterate through all subarrays of A; for each subarray we compute its minimum y, and increment B[y].

for (int i = 0; i < N; ++i) {
    int y = A[i];
    for (int j = i; j < N; ++j) {
        // minimum of subarray [i, j]
        y = min(y, A[j]);
        ++B[y];
    }
}

Since the limits of N are small, the above algorithm will suffice to solve the problem.

An O (N) algorithm:

In this section we present a linear time algorithm to compute the array B.

We define minPos(i, j) as smallest k, such that i <= k <= j, and A[k] is the minimum element of subarray A[i, j]. For a given k, there could be many pairs (i, j) such that minPos(i, j) = k.
Let us say that

  1. k1 < k is the smallest integer such that all elements in the subarray A[k1, k - 1] are strictly greater than A[k], and
  2. k2 > k is the largest integer that no element in the subarray A[k, k2] is strictly smaller than A[k].

Now, it is easy to see that minPos(i, j) = k if and only if k1 <= i <= k <= j <= k2.
This means there are exactly (k - k1 + 1) * (k2 - k + 1) such pairs (i, j) whose minPos is k.

If we can compute the integer k1 and k2 for each k, then we can compute the array B easily. We just need to iterate through the values of k from 0 to N-1, for each k, compute k1, k2, and hence the number of subarrays whose minPos() is k using the above formula. The element B[A[k]] will then be incremented by this value.

Next, we discuss how to compute k1’s in a single pass, the computation of k2 can be done in a similar way.
We scan the array A from left to right and maintain a sequence {v1, v2, …} such that:

  1. vi < vi+1,
  2. A[vi] <= A[vi+1],
  3. for each j in (vi, vi+1), A[j] > A[vi+1]
  4. the last element of the sequence is the index of the last scanned element.

Or, in other words (vi + 1) is the k1 value for vi+1. The sequence can be maintained easily. Whenever, we scan a new value A[i] = x in the array A, we just need to look at the sequence from right to left, and remove all the values j such that A[j] > x.

V = {};
for (int i = 0; i < N; ++i) {
    while (!V.empty() && A[V.back()] > A[i])
        V.pop_back();
        
    // If V is empty, then k1 value for i is 0, otherwise
    // k1 value for i is (1 + V.back())
    
    V.push_back(i);
}

Since each integer is added to V exactly once, and removed at most once, the time complexity of above algorithm is linear.

TIME COMPLEXITY:

O (N + Q)

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution will be put up soon.
Tester’s solution will be put up soon.

7 Likes
2

Please correct me if I am wrong!

I think the O(N^2) algorithm is actually O(N^3) since finding the minimum in the sub-array will take O(N).

3

You can compute the minimum of all subarrays in O (N^2) time as shown in the snippet.

1 Like
4

this is similar to the one posted above of O(n^2)
but gives wrong answer (please help)

for(i=0;i<n;++i)
{
min=a[i];
a[min]++;

for(j=i+1;j<n;++j)
{
if(a[j]<min)
min=a[j];

ans[min]++;

}
}