Given an array arr[] consisting of N integers, the task is to find the number of subarrays starting or ending at an index i such that arr[i] is the maximum element of the subarray.
Examples:
Input: arr[] = {3, 4, 1, 6, 2}
Output: 1 3 1 5 1
Explanation:
- The subarray starting or ending at index 0 and with maximum arr[0](=3) is {3}. Therefore, the count is 1.
- The subarrays starting or ending at index 1 and with maximum arr[1](=4) are {3, 4}, {4}, and {4, 1}. Therefore, the count is 3.
- The subarray starting or ending at index 2 and with maximum arr[2](=1) is {1}. Therefore, the count is 1.
- The subarrays starting or ending at index 3 and with maximum arr[3](=6) are {3, 4, 1, 6}, {4, 1, 6}, {1, 6}, {6}, and {6, 2}. Therefore, the count is 5.
- The subarray starting or ending at index 4 and with maximum arr[4](=2) is {2}. Therefore, the count is 1.
Input: arr[] = {1, 2, 3}
Output: 1 2 3
Naive Approach: The simplest approach to solve the given problem is for every ith index, iterate backward and forward until the maximum of the subarray remains equal to arr[i] and then print the total count of subarrays obtained.
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized by storing the index of the next greater element and previous greater element for every index i and find the count of subarrays accordingly for each index. Follow the steps below to solve the given problem:
- Initialize two arrays say pge[] and nge[] to store the index of the previous greater element and next greater element for each index i.
- Find the index of the Previous Greater Element for each index and store the resulting array in pge[].
- Find the index of the Next Greater Element for each index and store the resulting array in nge[].
- Iterate over the range [0, N – 1] and using the variable i and in each iteration print, the count of subarrays starting or ending at index i and with arr[i] as the maximum as nge[i] + pge[i] – 1 and print this count.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find previous greater// elementint* getPGE(int arr[], int n){ // Stores the previous greater // element for each index int* pge = new int[n]; stack<int> stack; // Traverse the array for(int i = 0; i < n; i++) { // Iterate until stack is empty // and top element is less than // the current element arr[i] while (!stack.empty() && arr[stack.top()] <= arr[i]) { stack.pop(); } // Update the previous greater // element for arr[i] pge[i] = stack.empty() ? -1 : stack.top(); // Push the current index to // the stack stack.push(i); } // Return the PGE[] array return pge;}// Function to find the Next Greater Elementint* getNGE(int arr[], int n){ // Stores the next greater element // for each index int* nge = new int[n]; stack<int> stack; // Traverse the array from the back for(int i = n - 1; i >= 0; i--) { // Iterate until stack is empty // and top element is less than // the current element arr[i] while (!stack.empty() && arr[stack.top()] <= arr[i]) { stack.pop(); } // Update the next greater // element for arr[i] nge[i] = stack.empty() ? n : stack.top(); // Push the current index stack.push(i); } // Return the NGE[] array return nge;}// Function to find the count of// subarrays starting or ending at// index i having arr[i] as maximumvoid countSubarrays(int arr[], int n){ // Function call to find the // previous greater element // for each array elements int* pge = getPGE(arr, n); // Function call to find the // previous greater element // for each elements int* nge = getNGE(arr, n); // Traverse the array arr[] for(int i = 0; i < n; i++) { // Print count of subarrays // satisfying the conditions cout << nge[i] - pge[i] - 1 << " "; }}// Driver Codeint main(){ int arr[] = { 3, 4, 1, 6, 2 }; int n = sizeof(arr) / sizeof(arr[0]); countSubarrays(arr, n); return 0;}// This code is contributed by Potta Lokesh |
Java
// Java program for the above approachimport java.util.*;public class GFG { // Function to find previous greater // element private static int[] getPGE(int[] arr) { // Stores the previous greater // element for each index int[] pge = new int[arr.length]; Stack<Integer> stack = new Stack<>(); // Traverse the array for (int i = 0; i < arr.length; i++) { // Iterate until stack is empty // and top element is less than // the current element arr[i] while (!stack.isEmpty() && arr[stack.peek()] <= arr[i]) { stack.pop(); } // Update the previous greater // element for arr[i] pge[i] = stack.isEmpty() ? -1 : stack.peek(); // Push the current index to // the stacl stack.push(i); } // Return the PGE[] array return pge; } // Function to find the Next Greater Element private static int[] getNGE(int[] arr) { // Stores the next greater element // for each index int[] nge = new int[arr.length]; Stack<Integer> stack = new Stack<>(); // Traverse the array from the back for (int i = arr.length - 1; i >= 0; i--) { // Iterate until stack is empty // and top element is less than // the current element arr[i] while (!stack.isEmpty() && arr[stack.peek()] <= arr[i]) { stack.pop(); } // Update the next greater // element for arr[i] nge[i] = stack.isEmpty() ? arr.length : stack.peek(); // Push the current index stack.push(i); } // Return the NGE[] array return nge; } // Function to find the count of // subarrays starting or ending at // index i having arr[i] as maximum private static void countSubarrays(int[] arr) { // Function call to find the // previous greater element // for each array elements int[] pge = getPGE(arr); // Function call to find the // previous greater element // for each elements int[] nge = getNGE(arr); // Traverse the array arr[] for (int i = 0; i < arr.length; i++) { // Print count of subarrays // satisfying the conditions System.out.print( nge[i] - pge[i] - 1 + " "); } } // Driver Code public static void main(String[] args) { int[] arr = new int[] { 3, 4, 1, 6, 2 }; countSubarrays(arr); }} |
Python3
# Python program for the above approach# Stores the previous greater# element for each indexpge = []# Stores the next greater element# for each indexnge = []# Function to find previous greater# elementdef getPGE(arr, n) : s = list() # Traverse the array for i in range(0, n): # Iterate until stack is empty # and top element is less than # the current element arr[i] while (len(s) > 0 and arr[s[-1]] <= arr[i]): s.pop() # Update the previous greater # element for arr[i] if len(s) == 0: pge.append(-1) else: pge.append(s[-1]) # Push the current index s.append(i) # Function to find the Next Greater Element def getNGE(arr, n) : s = list() # Traverse the array from the back for i in range(n-1, -1, -1): # Iterate until stack is empty # and top element is less than # the current element arr[i] while (len(s) > 0 and arr[s[-1]] <= arr[i]): s.pop() # Update the next greater # element for arr[i] if len(s) == 0: nge.append(n) else: nge.append(s[-1]) # Push the current index s.append(i) nge.reverse(); # Function to find the count of# subarrays starting or ending at# index i having arr[i] as maximumdef countSubarrays(arr, n): # Function call to find the # previous greater element # for each array elements getNGE(arr, n); # Function call to find the # previous greater element # for each elements getPGE(arr, n); # Traverse the array arr[] for i in range(0,n): print(nge[i]-pge[i]-1,end = " ")arr = [ 3, 4, 1, 6, 2 ]n = len(arr)countSubarrays(arr,n);# This code is contributed by codersaty |
C#
// C# program for the above approachusing System;using System.Collections;class GFG { // Function to find previous greater // element static int[] getPGE(int[] arr) { // Stores the previous greater // element for each index int[] pge = new int[arr.Length]; Stack stack = new Stack(); // Traverse the array for (int i = 0; i < arr.Length; i++) { // Iterate until stack is empty // and top element is less than // the current element arr[i] while (stack.Count > 0 && arr[(int)stack.Peek()] <= arr[i]) { stack.Pop(); } // Update the previous greater // element for arr[i] pge[i] = stack.Count == 0 ? -1 : (int)stack.Peek(); // Push the current index to // the stacl stack.Push(i); } // Return the PGE[] array return pge; } // Function to find the Next Greater Element static int[] getNGE(int[] arr) { // Stores the next greater element // for each index int[] nge = new int[arr.Length]; Stack stack = new Stack(); // Traverse the array from the back for (int i = arr.Length - 1; i >= 0; i--) { // Iterate until stack is empty // and top element is less than // the current element arr[i] while (stack.Count > 0 && arr[(int)stack.Peek()] <= arr[i]) { stack.Pop(); } // Update the next greater // element for arr[i] nge[i] = stack.Count == 0 ? arr.Length : (int)stack.Peek(); // Push the current index stack.Push(i); } // Return the NGE[] array return nge; } // Function to find the count of // subarrays starting or ending at // index i having arr[i] as maximum static void countSubarrays(int[] arr) { // Function call to find the // previous greater element // for each array elements int[] pge = getPGE(arr); // Function call to find the // previous greater element // for each elements int[] nge = getNGE(arr); // Traverse the array arr[] for (int i = 0; i < arr.Length; i++) { // Print count of subarrays // satisfying the conditions Console.Write((nge[i] - pge[i] - 1) + " "); } } // Driver code static void Main() { int[] arr = { 3, 4, 1, 6, 2 }; countSubarrays(arr); }}// This code is contributed by divyesh072019. |
Javascript
<script>// Javascript program for the above approach// Stores the previous greater// element for each indexlet pge = [];// Stores the next greater element// for each indexlet nge = [];// Function to find previous greater// elementfunction getPGE(arr, n) { let s = []; // Traverse the array for (let i = 0; i < n; i++) { // Iterate until stack is empty // and top element is less than // the current element arr[i] while (s.length > 0 && arr[s[s.length - 1]] <= arr[i]) { s.pop(); } // Update the previous greater // element for arr[i] if (s.length == 0) pge.push(-1); else pge.push(s[s.length - 1]); // Push the current index s.push(i); }}// Function to find the Next Greater Elementfunction getNGE(arr, n) { let s = []; // Traverse the array from the back for (let i = n - 1; i >= 0; i--) { // Iterate until stack is empty // and top element is less than // the current element arr[i] while (s.length > 0 && arr[s[s.length - 1]] <= arr[i]) { s.pop(); } // Update the next greater // element for arr[i] if (s.length == 0) nge.push(n); else nge.push(s[s.length - 1]); // Push the current index s.push(i); } nge.reverse();}// Function to find the count of// subarrays starting or ending at// index i having arr[i] as maximumfunction countSubarrays(arr, n) { // Function call to find the // previous greater element // for each array elements getNGE(arr, n); // Function call to find the // previous greater element // for each elements getPGE(arr, n); // Traverse the array arr[] for (let i = 0; i < n; i++) { document.write(nge[i] - pge[i] - 1 + " "); }}let arr = [3, 4, 1, 6, 2];let n = arr.length;countSubarrays(arr, n);// This code is contributed by _saurabh_jaiswal</script> |
Output:
1 3 1 5 1
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
