Count Subarrays where Second Highest lies before Highest

Last Updated on October 3, 2022 by Ria Pathak

Problem Statement

You will be given an array of N distinct elements. The minimum value of N is 2. In every subarray of the given array, you have to find such pairs (x,y), where x is the index of the second largest element of the subarray, and y is the index of the largest element of the subarray such that x < y. Your task is to return the total number of such distinct pairs in an array.

Example

Let us consider the array and its subarrays shown below.

Now, for the second highest and highest to exist, the size of the subarray should at least be 2. So, the subarrays {4}, {6}, {5} and {7} have 0 such pairs.

Now, in the subarray {4,6}, we have the second highest at index 1 and highest element at index 2 (1-based indexing). Also, the index of the second highest element is less than that of the highest element. Hence, we have found a valid pair.

Now, for the subarray {6,5}, the index of the second largest element is greater than the index of the largest element. Hence, no valid pair is found here.

For the subarray {5,7}, the valid pair is {1,2}. Since we already have that pair from the subarray {4,6}, we won’t consider it as we want distinct pairs.

Now, the subarray {4,6,5} has the second highest element at index 3 and the highest at index 2 which does not follow x < y, hence it has 0 valid pairs.

In the subarray {6,5,7}, the index of the second highest element is 2 and the index of the highest element is 3. So, we have a valid pair {1,3}.

Finally, from the entire array, the index of the second largest element is 2 and the index of the largest element is 4. So, we have a valid pair {2,4}. Hence, we have 3 valid pairs. So, the count is 3.

Brute Force Approach (Intuition)

We know the brute force approach will be to generate all the subarray and maintain the pairs with us. So, in each subarray, we find the index of the largest and the second largest element and try to see if the pair exists or not. If it is a valid pair that does not exist, consider that pair, else leave it. The time complexity of this approach will be O(N2) and space complexity will be O(P) where P is the number of valid pairs.

Approach (Using Stack)

So, we know that the brute force approach is quadratic in time complexity. We can however solve this problem in linear time complexity as well. We can use the concept of Next Greater Element (NGE).

Let us consider an array shown below.

Let us say the current index at which we are is index 4.

Let us say that prev is the index of the Next Greater Element (NGE) to the left of current. So, prev = 1. Also, let us say that next is the index of the NGE towards the right of the current index. So, next = 6.

Now, observe that all the subarrays with starting index in the range [prev + 1, z] (both inclusive) and ending at index “next”, have the second largest element at index = curr and the largest element at index = next.

We can also observe that there are (curr – prev) valid pairs in these subarrays.

So, this means that we just have to know the NGE to the left and right of each index and then add curr – prev for all the indices to get the total number of valid pairs.

Now, the only thing which remains is to discuss how to calculate NGE to the right and left. So, let us discuss the same.

Note: In further discussion, the L array is the array that contains NGE to left, and the R array is the array that contains NGE to the right.

Next Greater Element (NGE) to the Left

Consider the array shown below.

So, we have an empty L array that we have to fill. Let us take a Stack and let us take a pointer at index 0 as shown below.

For index 0, there is no element to the left. Hence, there will not be any NGE to the left. So, L[0] = 0, and we push the index 0 into the stack.

Now, array[i] = array[1] = 8 is less than array[top of stack]. So, the top of the stack will become the next greater element (NGE) to the left for index 1. Hence, L[1] = 0.

However, in the question, since we are given 1-based indexing, L[1] = top of stack + 1. Hence, L[1] = 0+1 = 1.

We will also push the current index into the stack because the element at our index can be an NGE for some other index moving forward.

So, we can establish the following conclusion from above.

So, using this conclusion, we can fill our answers till index 3 as shown below.

Now, at index 4, arr[i] > arr[top]. So, we have to pop from the stack till the stack is not empty and arr[i] > arr[top].

So, after popping the elements from the stack, the next step is same as above.

So, the conclusion that we derive from here is shown below.

One thing is left to discuss. What if we keep popping from the stack and it becomes empty? Consider the case when i moves to the next index i.e. index 5.

In this case, value at index 5 is greater than all the other values. So, the stack becomes empty. In this case, stack being empty means that there is no NGE to the left. Hence, L[i] = 0. Also, we will push the current index into the stack.

So, the conclusion derived from here is shown below.

Now, try filling the last index of L array yourself. It is as shown below.

So, we have completely filled the L array. Now, we have to fill the R array. Let us discuss it.

Next Greater Element (NGE) to the Right

This process is a little bit different from the previous one. Here, let us assume that we have once filled the array with all 0s and have already pushed the 0 index into the stack as shown below.

We start iterating from index 1. Since arr[i] = arr[1] = 8 < arr[top], i cannot be the NGE index for the top of the stack i.e. index 0. However, it can be an NGE index for some other index moving forward. Hence, we will push it into the stack.

The conclusion that we devise from here is given below.

So, with this conclusion, we will move till index 3 and no change will take place in the R array.

Now, arr[i] = arr[4] = 4 is greater than arr[top] = arr[3] = 3. So, i=4 will be the NGE index for the top of the stack. Hence, we pop it from the stack, and R[top] = i + 1. We have done plus 1 because the indices in the question are 1-based.

Also, we will do this till the stack is not empty and arr[i] > arr[top].

The conclusion that we draw from here is shown below.

So, when we are at index = 5, we can see this better as shown below.

Finally, the R array gets completely filled.

So, we have learned the Next Greater Element to the Right.
So, now that we have understood the complete procedure, let us write the code for the same.

#include 
#define MAXN 100005
using namespace std;

void NGE_To_Right(int arr[], int n, int nextBig[])
{
	stack > s;

	for (int i = n - 1; i >= 0; i--) {

		nextBig[i] = i;
		while (!s.empty() && s.top().first < arr[i])
			s.pop();

		if (!s.empty())
			nextBig[i] = s.top().second;

		s.push(pair(arr[i], i));
	}
}

void NGE_To_Left(int arr[], int n, int prevBig[])
{
	stack > s;
	for (int i = 0; i < n; i++) {

		prevBig[i] = -1;
		while (!s.empty() && s.top().first < arr[i])
			s.pop();

		if (!s.empty())
			prevBig[i] = s.top().second;

		s.push(pair(arr[i], i));
	}
}

int count_valid_pairs(int arr[], int n)
{
	int nextBig[MAXN];
	int prevBig[MAXN];
	int maxi[MAXN];
	int ans = 0;

	NGE_To_Left(arr, n, prevBig);

	NGE_To_Right(arr, n, nextBig);

	for (int i = 0; i < n; i++)
		if (nextBig[i] != i)
			maxi[nextBig[i] - i] = max(maxi[nextBig[i] - i],i - prevBig[i]);

	for (int i = 0; i < n; i++)
		ans += maxi[i];

	return ans;
}

int main()
{
	int arr[] = {4,6,5,7};
	int n = sizeof(arr) / sizeof(arr[0]);
	cout << count_valid_pairs(arr, n) << endl;
	return 0;
}

import java.util.*;

public class Main
{
	
    static int MAXN = 100005;
    
    static class pair
    {
    	int first, second;
    	public pair(int first, int second)
    	{
    		this.first = first;
    		this.second = second;
    	}
    }
    
    static void NGEToRight(int arr[], int n, int nextBig[])
    {
    	Stack s = new Stack<>();
    
    	for (int i = n - 1; i >= 0; i--)
    	{
    
    		nextBig[i] = i;
    		while (!s.empty() && s.peek().first < arr[i])
    			s.pop();
    
    		if (!s.empty())
    			nextBig[i] = s.peek().second;
    
    		s.push(new pair(arr[i], i));
    	}
    }
    
    static void NGEToLeft(int arr[], int n, int prevBig[])
    {
    	Stack s = new Stack<>();
    	for (int i = 0; i < n; i++)
    	{
    
    		prevBig[i] = -1;
    		while (!s.empty() && s.peek().first < arr[i])
    			s.pop();
    
    		if (!s.empty())
    			prevBig[i] = s.peek().second;
    
    		s.push(new pair(arr[i], i));
    	}
    }
    
    static int countValidPairs(int arr[], int n)
    {
    	int []nextBig = new int[MAXN];
    	int []prevBig = new int[MAXN];
    	int []maxi = new int[MAXN];
    	int ans = 0;
    
    	NGEToLeft(arr, n, prevBig);
    
    	NGEToRight(arr, n, nextBig);
    
    	for (int i = 0; i < n; i++)
    		if (nextBig[i] != i)
    			maxi[nextBig[i] - i] = Math.max(maxi[nextBig[i] - i],i - prevBig[i]);
    
    	for (int i = 0; i < n; i++)
    		ans += maxi[i];
    
    	return ans;
    }
    
    
    public static void main(String[] args)
    {
    
    	int arr[] = {4,6,5,7};
    	int n = arr.length;
    
    	System.out.println(countValidPairs(arr, n));
    }
}

Time Complexity

The time complexity for this algorithm is O(N). This is because we are calculating the NGE towards left and right which takes O(N) time each. Then, we are simply traversing the entire array to add all the values up.

Space Complexity

The space complexity is O(N) as we use two arrays for having the NGEs to the left and right.

This article tried to discuss How to Count Subarrays where Second Highest lies before Highest. Hope this blog helps you understand and solve the problem. To practice more problems you can check out MYCODE | Competitive Programming at Prepbytes.
.