Count elements in Array having strictly smaller and strictly greater element present

0 0 7 minutes read

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);

Output

Time Complexity: O(N²)
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>

Output

Time Complexity: O(N)
Auxiliary Space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!