Given an array A that is a permutation of n numbers (1~n)
eg. [4 3 1 2 5]
Find the number of subarrarys S that meets the following condition
max(S)-min(S)=length(S)-1
For the above example,
eg. [4 3 1 2 5]
subarrays that meets the condition are
[4]
[3]
[1]
[2]
[5]
[4 3]
[1 2]
[3 1 2]
[4 3 1 2]
[4 3 1 2 5]
There are 10 subarray that meets the condition
So the answer should be 10
Where did u get this problem from? What’s the required complexity?
1 Like
I was asked in an interview last week
The interviewer specify that it could be done using
three pointers and sliding window
or maybe even better
But I only come up with an solution
maintaining the max and min array in two different arrays
then iterate through all the possibilities
Which isn’t fast enough
1 Like
I don’t think there’s a faster way than O(N^2), where N is the length of the array.
Here's a C++14 code demonstrating my process
#include <iostream>
#include <vector>
int solve (const std::vector<int>& V) {
// This is an O(N ^ 2) approach.
// We iterate over all subarrays
// V_l ... V_r, updating the min
// and max elements each time.
// (r - l + 1) denotes the size
// of the current subarray.
// For each subarray, we simply
// check whether the difference
// between the max and min
// elements match up with
// the current length - 1
// and increment the variable
// that stores our answer.
// since each subarray of length 1
// forms an acceptable subarray
int number_of_subarrays = V.size();
for (int l = 0; l < V.size(); ++l) {
// initializing min and max
int min = V[l];
int max = V[l];
for (int r = l + 1; r < V.size(); ++r) {
// updating min and max
if (min > V[r]) {
min = V[r];
} else if (max < V[r]) {
max = V[r];
}
int difference = max - min;
int current_length_minus_1 = r - l;
// checking for match
if (difference == current_length_minus_1) {
++number_of_subarrays;
}
}
}
return number_of_subarrays;
}
int main (void) {
int N;
scanf("%d", &N);
std::vector<int> V(N);
for (auto& e : V)
scanf("%d", &e);
printf("%d\n", solve(V));
return 0;
}
Why don’t I think there’s a faster way?
Let’s think about the worst case, where the given permutation is the identity permutation,
i.e., [1, 2, 3, ..., N].
The answer would be \displaystyle \frac{N \times (N+1)} {2} as all possible subarrays form an acceptable subarray.
Three pointers technique
I have never heard of this technique. Do enlighten me, anyone. 
Sliding window technique
I’ve known that this method is used to convert O(N \times K) techniques to O(N), where K is the window size. In this problem, we can see that the window size \in [1, N].
We can iterate over the entire array and fill buckets \in [1, N], storing the number of subarrays of the size corresponding to each index. After that, we may sum up the weights of the buckets in O(N).
But, as we see in the worst case, for bucket index B there are N - B + 1 subarrays. The total effort put into filling each bucket can be indicated by the sum of the weights of each bucket, i.e.,
\displaystyle \sum _{B = 1} ^ {B = N} (N - B + 1)
= \displaystyle \sum _{B = 1} ^ {B = N} (N) - \sum _{B = 1} ^ {B = N} (B ) + \sum _{B = 1} ^ {B = N} (1)
= \displaystyle (N \times N) - \frac {N \times (N + 1)} {2} + N
= \displaystyle \frac {N \times (N + 1)} {2}
which again, \in O(N ^ 2). So, I don’t really think we can go faster than this.
Please prove me wrong anyone. 
3 Likes
Thank you for your efforts!! :)
I did an O(n^2) approach on Google's interview like yours
but interviewer said it could be better
I forgot to mention that the interviewer mentioned that
the three pointers method is actually like the two pointers method with a slightly modification
I remember the interviewer did give another special approach which I still can't get
I'll try to explain below
First, we'll divide the array to left and right half (just like divide and conquer)
[][][][] | [][][][]
then we maintain two arrays Max array and Min array for each half
(so 4 arrays, 2 for left(max, min), 2 for right(max, min))
which means the max or min of k numbers "counting from the middle" "|"
eg. For array 4 5 2 3 6 8 1 7
Divide
4 5 2 3 | 6 8 1 7
Max Array Left Max Array Right
5 5 3 3 6 8 8 8
Min Array Left Min Array Right
2 2 2 3 6 6 1 1
We then can observe that 4 arrays would be "monotone sequence"
which means that it will decrease in one way, or increase in one way
eg. For the above example
Max Array Left => Increase from right to left
Max Array Right => Increase from left to right
Min Array Left => Decrease from right to left
Min Array Right => Decrease from left to right
Then when we combine the left and right half,
There are only 4 conditions
Max Left > Max Right & Min Left > Min Right
Max Left > Max Right & Min Left < Min Right
Max Left < Max Right & Min Left > Min Right
Max Left < Max Right & Min Left < Min Right
The algorithm is basically like that,
but I have a hard time understanding it
I'll fill in more details that I remember
Thanks all of you
1 Like
I guess you’re aiming at an O(N \times log N) approach. Interesting!
I wonder why you omitted the case where the operands may be equal.
So, the set of operators is S = \{<, >, =\}.
\therefore number of possibilities = |S|^2 = 3^2 = 9
1 Like
Because the whole array A is a permutation of n numbers (1~n)
So doesn't that mean the left and right half won't be equal? :)
1 Like
Oh yes. I got confused trying to understand the algorithm.
1 Like
I didn’t understand the final part of this solution. How does the 4 conditions help in getting the matching subarray count