Count subarrays where second highest lie before highest

Problem Statement

The problem “Count subarrays where second highest lie before highest” states that you are given an array a[ ] of size n where n is greater than or equal to 2. Count the total number of subarrays in which the index of highest element of the subarray is greater than the index of second highest element of the subarray.

Example

 a[ ] = {1, 3, 2, 4}

3

a[ ] = {1, 2, 3}

2

Algorithm

1. Initialize an array a[ ] of size n.
2. Create three arrays to store previous big element, next big element and maximum element respectively. Declare a variable to store the answer and set it’s value as 0.
3. Create a stack of pairs of type integer.
4. Traverse from 0 to n-1 and set the value of current index of previous big element array as -1. While stack is not empty and the first element from the pair at the top of the stack is less than the element at current index in array a[ ], pop/delete the pair at top of the stack.
5. If the size of the stack is not 0, update the value of current index of previous big element array as the second element from the pair at the top of the stack.
6. Form the pair of the element at current index in array a[ ] and the current index. Push/insert the pair in the stack.
7. Create another stack of pairs of type integer.
8. Traverse from n-1 to 0 and set the value of current index of next big element array as the current index. While stack is not empty and the first element from the pair at the top of the stack is less than the element at current index in array a[ ], pop/delete the pair at top of the stack.
9. If the size of the stack is not 0, update the value of current index of next big element array as the second element from the pair at the top of the stack.
10. Form the pair of the element at current index in array a[ ] and the current index. Push/insert the pair in the stack.

Code

C++ Program to count subarrays where second highest lie before highest

#include <iostream>
#include <stack>
#define MAXN 100005 
using namespace std; 
  
void makeNext(int arr[], int n, int nextBig[]){ 
    stack<pair<int, int> > 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<int, int>(arr[i], i)); 
    } 
} 
  
void makePrev(int arr[], int n, int prevBig[]){ 
    stack<pair<int, int> > 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<int, int>(arr[i], i)); 
    } 
} 
  
int wrapper(int arr[], int n){ 
    int nextBig[MAXN]; 
    int prevBig[MAXN]; 
    int maxi[MAXN]; 
    int ans = 0; 
  
    makePrev(arr, n, prevBig); 
  
    makeNext(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 a[] = { 1, 3, 2, 4 }; 
    int n = sizeof(a) / sizeof(a[0]);
    
    cout << wrapper(a, n) << endl; 
    
    return 0; 
}

3

Java Program to count subarrays where second highest lie before highest

import java.util.*; 
  
class CountSubarray{ 
      
    static int MAXN = 100005; 
      
    static class pair{  
        int first, second;
        
        public pair(int first, int second){  
            this.first = first;  
            this.second = second;  
        }  
    } 
    
    static void makeNext(int arr[], int n, int nextBig[]){ 
        Stack<pair> 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 makePrev(int arr[], int n, int prevBig[]){ 
        Stack<pair> 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 wrapper(int arr[], int n){
        
        int []nextBig = new int[MAXN]; 
        int []prevBig = new int[MAXN]; 
        int []maxi = new int[MAXN]; 
        int ans = 0; 
      
        makePrev(arr, n, prevBig); 
      
        makeNext(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 a[] = { 1, 3, 2, 4 }; 
        int n = a.length; 
      
        System.out.println(wrapper(a, n)); 
    } 
}

3

Complexity Analysis

Time Complexity

O(n) where n is the number of elements in the array a[ ]. Since we have only traversed over the input array and pushed them or removed them from stack. The time complexity is linear.

Space Complexity

O(n) because we used space for n elements. We were only storing the elements from the input into the stack. Since the number of elements was N, the space complexity is also linear.