Given an array arr[], the task is to find the count of elements in the given array such that there exists an element strictly smaller and an element strictly greater than it.
Examples:
Input: arr [] = {11, 7, 2, 15}
Output: 2
Explanation: For arr[1] = 7, arr[0] is strictly greater than it and arr[2] is strictly smaller than it. Similarly for arr[1], arr[3] is strictly greater than it and arr[2] is strictly smaller than it. Hence, the required count is 2.Input: arr[] = {1, 1, 1, 3}
Output: 0
Naive Approach: The given problem can be solved by iterating over each element of the array arr[] and checking whether there exists a strictly greater and strictly smaller element than it.
Algorithm:
- Initialize a variable ‘count‘ to 0 to keep track of the number of elements that satisfy the condition.
- Traverse each element of the array using a loop with index ‘i’.
- For each element, traverse the array again using a nested loop with index ‘j’ and check if there exists an element strictly smaller and an element strictly greater than the current element arr[i].
- If such elements exist, increase the ‘count‘ variable.
- Return the final value of ‘count‘.
Below is the implementation of the approach:
C++
// C++ code for the approach #include <bits/stdc++.h> using namespace std; // Function to count elements // which satisfy the condition int countElements( int arr[], int n) { int count = 0; // traverse each element for ( int i = 0; i < n; i++) { bool smaller = false , greater = false ; for ( int j = 0; j < n; j++) { if (i != j) { if (arr[j] < arr[i]) smaller = true ; else if (arr[j] > arr[i]) greater = true ; } } // if both strictly smaller and // greater exists, increase count if (smaller && greater) count++; } return count; } // Driver's code int main() { // Input int arr[] = { 11, 7, 2, 15 }; int n = sizeof (arr) / sizeof (arr[0]); // Function call int count = countElements(arr, n); // Output cout << count; return 0; } |
Java
public class Main { // Function to count elements that satisfy the condition public static int countElements( int [] arr) { int n = arr.length; int count = 0 ; // Loop through each element for ( int i = 0 ; i < n; i++) { boolean smaller = false , greater = false ; for ( int j = 0 ; j < n; j++) { if (i != j) { if (arr[j] < arr[i]) smaller = true ; else if (arr[j] > arr[i]) greater = true ; } } // If both strictly smaller and greater elements exist, increase count if (smaller && greater) count++; } return count; } public static void main(String[] args) { // Input int [] arr = { 11 , 7 , 2 , 15 }; // Function call int count = countElements(arr); // Output System.out.println(count); } } |
Python3
def count_elements(arr): count = 0 # Traverse each element for i in range ( len (arr)): smaller, greater = False , False for j in range ( len (arr)): if i ! = j: if arr[j] < arr[i]: smaller = True elif arr[j] > arr[i]: greater = True # If both strictly smaller and greater elements exist, increase count if smaller and greater: count + = 1 return count # Driver's code arr = [ 11 , 7 , 2 , 15 ] count = count_elements(arr) print (count) |
C#
using System; public class GFG { // Function to count elements // which satisfy the condition public static int CountElements( int [] arr, int n) { int count = 0; // traverse each element for ( int i = 0; i < n; i++) { bool smaller = false , greater = false ; for ( int j = 0; j < n; j++) { if (i != j) { if (arr[j] < arr[i]) smaller = true ; else if (arr[j] > arr[i]) greater = true ; } } // if both strictly smaller and // greater exists, increase count if (smaller && greater) count++; } return count; } public static void Main() { // Input int [] arr = { 11, 7, 2, 15 }; int n = arr.Length; // Function call int count = CountElements(arr, n); // Output Console.WriteLine(count); } } |
Javascript
// JS code for the approach // Function to count elements // which satisfy the condition function countElements(arr, n) { let count = 0; // traverse each element for (let i = 0; i < n; i++) { let smaller = false , greater = false ; for (let j = 0; j < n; j++) { if (i != j) { if (arr[j] < arr[i]) smaller = true ; else if (arr[j] > arr[i]) greater = true ; } } // if both strictly smaller and // greater exists, increase count if (smaller && greater) count++; } return count; } // Driver's code // Input let arr = [ 11, 7, 2, 15 ]; let n = arr.length; // Function call let count = countElements(arr, n); // Output console.log(count); |
2
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized by finding the minimum and maximum element of the given array, traversing the given array arr[], and checking if arr[i] is strictly greater than the minimum and strictly smaller than the maximum. Maintain the count of such indices in a variable which is the required answer.
Below is the implementation of the above approach:
C++
// C++ Program of the above approach #include <bits/stdc++.h> using namespace std; // Function to find the count of elements // in the given array such that there exists // a strictly smaller and greater element int cntElements(vector< int >& arr) { // Stores the maximum int a = *max_element( arr.begin(), arr.end()); // Stores the minimum int b = *min_element( arr.begin(), arr.end()); // Stores the required count int cnt = 0; // Loop to iterate arr[] for ( auto x : arr) { // If x is valid if (x < a && x > b) cnt++; } // Return Answer return cnt; } // Driver Code int main() { vector< int > arr = { 11, 7, 2, 15 }; cout << cntElements(arr); return 0; } |
Java
// Java Program of the above approach import java.util.*; public class GFG { // Function to find the count of elements // in the given array such that there exists // a strictly smaller and greater element static int cntElements( int [] arr) { // Stores the required count int cnt = 0 ; // Stores the maximum int a = arr[ 0 ]; // Stores the minimum int b = arr[ 0 ]; for ( int i = 1 ; i < arr.length; i++) { if (arr[i] > a) { a = arr[i]; } if (arr[i] < b) { b = arr[i]; } } // Loop to iterate arr[] for ( int i = 0 ; i < arr.length; i++) { // If x is valid if (arr[i] < a && arr[i] > b) cnt++; } // Return Answer return cnt; } // Driver Code public static void main(String args[]) { int [] arr = { 11 , 7 , 2 , 15 }; System.out.print(cntElements(arr)); } } // This code is contributed by Samim Hossain Mondal. |
Python3
# Python code for the above approach # Function to find the count of elements # in the given array such that there exists # a strictly smaller and greater element def cntElements(arr): # Stores the maximum a = max (arr) # Stores the minimum b = min (arr) # Stores the required count cnt = 0 # Loop to iterate arr[] for x in range ( len (arr)): # If x is valid if arr[x] < a and arr[x]> b: cnt = cnt + 1 # Return Answer return cnt # Driver Code arr = [ 11 , 7 , 2 , 15 ]; print (cntElements(arr)); # This code is contributed by Potta Lokesh |
C#
// C# Program of the above approach using System; class GFG { // Function to find the count of elements // in the given array such that there exists // a strictly smaller and greater element static int cntElements( int [] arr) { // Stores the required count int cnt = 0; // Stores the maximum int a = arr[0]; // Stores the minimum int b = arr[0]; for ( int i = 1; i < arr.Length; i++) { if (arr[i] > a) { a = arr[i]; } if (arr[i] < b) { b = arr[i]; } } // Loop to iterate arr[] for ( int i = 0; i < arr.Length; i++) { // If x is valid if (arr[i] < a && arr[i] > b) cnt++; } // Return Answer return cnt; } // Driver Code public static int Main() { int [] arr = { 11, 7, 2, 15 }; Console.Write(cntElements(arr)); return 0; } } // This code is contributed by Taranpreet |
Javascript
<script> // JavaScript Program of the above approach // Function to find the count of elements // in the given array such that there exists // a strictly smaller and greater element const cntElements = (arr) => { // Stores the maximum let a = Math.max(...arr); // Stores the minimum let b = Math.min(...arr); // Stores the required count let cnt = 0; // Loop to iterate arr[] for (let x in arr) { // If x is valid if (arr[x] < a && arr[x] > b) cnt++; } // Return Answer return cnt; } // Driver Code let arr = [11, 7, 2, 15]; document.write(cntElements(arr)); // This code is contributed by rakeshsahni </script> |
2
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!