Count array elements having at least one smaller element on its left and right side
Given an array arr[] of length N, the task is to find the number of elements in array arr[] which contains at least one smaller element on its left and right.
Examples:
Input: arr[] = {3, 9, 4, 6, 7, 5}
Output: 3
Explanation: Following 3 array elements satisfy the necessary conditions:
- arr[1] (= 9) has smaller element on left as 3 and on the right as 4
- arr[3] (= 6) has smaller element on left as 4 and on the right as 5.
- arr[4] (= 7) has smaller element on left as 6 and on the right as 5.
Input: arr[] = {3, 9, 14, 61, 17, 5, 12, 9, 15}
Output: 5
Naive Approach: The simplest approach is to traverse the given array and for each element, count the number of smaller elements both on its left and right. If both the counts are found to be at least 1, increase the answer by 1. Finally, print the answer obtained.
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to use a Stack. Maintain an increasing stack of elements to count the smaller element in constant time. Follow the steps below to solve the problem:
- Initialize a stack and a variable count as 0 as a count of numbers that satisfy the given condition.
- Traverse the given array using the variable i and perform the following steps:
- Iterate until the stack is not empty and the current element is less than the top element of the stack then:
- The element on top of the stack has a smaller element on right i.e., arr[i].
- If the stack size is greater than 1, then there is also a smaller element on left, as the stack has been maintained as an increasing stack.
- If the above conditions are true, then increment the count by 1.
- Pop the top element from the stack.
- Push the current element into the stack.
- Iterate until the stack is not empty and the current element is less than the top element of the stack then:
- After the above steps, the value of count gives the resultant count.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> #include <iostream> using namespace std; // Function to count the number of // elements that have smaller on // left and right side void findElements( int * arr, int N) { // Initialize stack stack< int > stack; // Stores the required count // of array elements int count = 0; // Traverse the array A{] for ( int i = 0; i < N; i++) { // If stack is not empty // and stack top > arr[i] while (!stack.empty() && arr[i] < stack.top()) { // If stack size > 1 if (stack.size() > 1) // Increment count count++; // Pop the top element stack.pop(); } // Push the element arr[i] stack.push(arr[i]); } // Print the final count cout << count; } // Driver Code int main() { int arr[] = { 3, 9, 4, 6, 7, 5 }; int N = sizeof (arr) / sizeof (arr[0]); // Function Call findElements(arr, N); return 0; } |
Java
// Java program for the // above approach import java.util.*; class GFG{ // Function to count the number of // elements that have smaller on // left and right side static void findElements( int [] arr, int N) { // Initialize stack Stack<Integer> stack = new Stack<>(); // Stores the required count // of array elements int count = 0 ; // Traverse the array A[] for ( int i = 0 ; i < N; i++) { // If stack is not empty // and stack top > arr[i] while (!stack.isEmpty() && arr[i] < stack.peek()) { // If stack size > 1 if (stack.size() > 1 ) // Increment count count++; // Pop the top element stack.pop(); } // Push the element arr[i] stack.add(arr[i]); } // Print the final count System.out.print(count); } // Driver Code public static void main(String[] args) { int arr[] = { 3 , 9 , 4 , 6 , 7 , 5 }; int N = arr.length; // Function Call findElements(arr, N); } } // This code is contributed by shikhasingrajput |
Python3
# Python3 program for the above approach # Function to count the number of # elements that have smaller on # left and right side def findElements(arr, N): # Initialize stack stack = [] # Stores the required count # of array elements count = 0 # Traverse the array A{] for i in range (N): # If stack is not empty # and stack top > arr[i] while ( len (stack) > 0 and arr[i] < stack[ - 1 ]): # If stack size > 1 if ( len (stack) > 1 ): # Increment count count + = 1 # Pop the top element del stack[ - 1 ] # Push the element arr[i] stack.append(arr[i]) # Print the final count print (count) # Driver Code if __name__ = = '__main__' : arr = [ 3 , 9 , 4 , 6 , 7 , 5 ] N = len (arr) # Function Call findElements(arr, N) # This code is contributed by mohit kumar 29 |
C#
// C# program for the // above approach using System; using System.Collections.Generic; class GFG{ // Function to count the number of // elements that have smaller on // left and right side static void findElements( int [] arr, int N) { // Initialize stack Stack< int > stack = new Stack< int >(); // Stores the required count // of array elements int count = 0; // Traverse the array A{] for ( int i = 0; i < N; i++) { // If stack is not empty // and stack top > arr[i] while (stack.Count != 0 && arr[i] < stack.Peek()) { // If stack size > 1 if (stack.Count > 1) // Increment count count++; // Pop the top element stack.Pop(); } // Push the element arr[i] stack.Push(arr[i]); } // Print the readonly count Console.Write(count); } // Driver Code public static void Main(String[] args) { int []arr = { 3, 9, 4, 6, 7, 5 }; int N = arr.Length; // Function Call findElements(arr, N); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript program for the above approach // Function to count the number of // elements that have smaller on // left and right side function findElements(arr, N) { // Initialize stack var stack = []; // Stores the required count // of array elements var count = 0; // Traverse the array A{] for ( var i = 0; i < N; i++) { // If stack is not empty // and stack top > arr[i] while (stack.length!=0 && arr[i] < stack[stack.length-1]) { // If stack size > 1 if (stack.length > 1) // Increment count count++; // Pop the top element stack.pop(); } // Push the element arr[i] stack.push(arr[i]); } // Print the final count document.write( count); } // Driver Code var arr = [3, 9, 4, 6, 7, 5]; var N = arr.length; // Function Call findElements(arr, N); </script> |
3
Time Complexity: O(N)
Auxiliary Space: O(N)