Home » Technical Interview Questions » Stack Interview Questions » Count subarrays where second highest lie before highest

Count subarrays where second highest lie before highest


Reading Time - 5 mins


Difficulty Level Medium

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.

Count subarrays where second highest lie before highest

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.
READ  The Stock Span Problem

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.

READ  Postfix to Infix Conversion

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.

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions